Submission #1239746


Source Code Expand

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <cmath>
using namespace std;

#define int long long
typedef pair<int, int> P;
#define rep(i, n) for (int i=0; i<(n); i++)
#define all(c) (c).begin(), (c).end()
#define uniq(c) c.erase(unique(all(c)), (c).end())
#define _1 first
#define _2 second
#define pb push_back
#define INF 1145141919
#define MOD 1000000007

long long X;
int N;
vector<P> G[100000];
bool centroid[100000];
int subtree_size[100000];

int compute_subtree_size(int v, int prev) {
  int c = 1;
  for (int i=0; i<G[v].size(); i++) {
    int t = G[v][i].first;
    if (t == prev || centroid[t]) continue;
    c += compute_subtree_size(t, v);
  }
  return subtree_size[v] = c;
}

P search_centroid(int v, int prev, int t) {
  P ret = P(INF, -1);
  int s = 1, m = 0;
  for (int i=0; i<G[v].size(); i++) {
    int w = G[v][i].first;
    if (w == prev || centroid[w]) continue;
    ret = min(ret, search_centroid(w, v, t));
    m = max(m, subtree_size[w]);
    s += subtree_size[w];
  }
  m = max(m, t - s);
  ret = min(ret, P(m, v));
  return ret;
}

void enumerate_paths(int v, int prev, int d, vector<int> &ds) {
  ds.push_back(d);
  for (int i=0; i<G[v].size(); i++) {
    int w = G[v][i].first;
    if (w == prev || centroid[w]) continue;
    enumerate_paths(w, v, d ^ G[v][i].second, ds);
  }
}

int count_pairs(vector<int> &ds) {
  map<int, int> m;
  for (int x : ds) m[x]++;

  int ctr = 0;
  for (auto &p : m) {
    int t = p._1 ^ X;
    if (p._1 == t) {
      ctr += (p._2) * (p._2-1);
    }
    else {
      if (m.find(t) != m.end()) ctr += (p._2) * m[t];
    }
  }
  m.clear();
  return ctr/2;
}

// 頂点vが属する部分木がいくつ有効なペアを持っているか
int solve_subproblem(int v) {
  int ret = 0;

  compute_subtree_size(v, -1);
  int s = search_centroid(v, -1, subtree_size[v]).second;
  centroid[s] = true;

  // [1] { a,b } <- s
  for (int i=0; i<G[s].size(); i++) {
    int w = G[s][i].first;
    if (centroid[w]) continue;
    ret += solve_subproblem(w);
  }
  // [2] { a } <- s -> { b }
  // [3] { a } <- s=b
  // 頂点sを通る頂点の組に関して数える
  vector<int> ds;
  ds.push_back(0);
  for (int i=0; i<G[s].size(); i++) {
    int w = G[s][i].first;
    if (centroid[w]) continue;
    vector<int> tds;
    enumerate_paths(w, s, G[s][i].second, tds);
    ret -= count_pairs(tds); // 重複分をあらかじめ引いておく
    ds.insert(ds.end(), tds.begin(), tds.end()); // append
  }
  ret += count_pairs(ds);

  centroid[s] = false;
  return ret;
}

signed main() {
  ios::sync_with_stdio(false); cin.tie(0);
  cin >> N >> X;
  for (int i=0; i<N-1; i++) {
    int u, v, l;
    cin >> u >> v >> l;
    G[u-1].push_back(P(v-1, l));
    G[v-1].push_back(P(u-1, l));
  }
  cout << solve_subproblem(0) << "\n";
  return 0;
}

Submission Info

Submission Time
Task C - エックスオア多橋君
User funcsr
Language C++14 (GCC 5.4.1)
Score 100
Code Size 3022 Byte
Status AC
Exec Time 695 ms
Memory 22708 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 100 / 100
Status
AC × 3
AC × 27
Set Name Test Cases
Sample subtask0_sample_01.txt, subtask0_sample_02.txt, subtask0_sample_03.txt
All subtask0_sample_01.txt, subtask0_sample_02.txt, subtask0_sample_03.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask1_15.txt, subtask1_16.txt, subtask1_17.txt, subtask1_18.txt, subtask1_19.txt, subtask1_20.txt, subtask1_21.txt, subtask1_22.txt, subtask1_23.txt, subtask1_24.txt
Case Name Status Exec Time Memory
subtask0_sample_01.txt AC 2 ms 2560 KB
subtask0_sample_02.txt AC 2 ms 2560 KB
subtask0_sample_03.txt AC 2 ms 2560 KB
subtask1_01.txt AC 2 ms 2560 KB
subtask1_02.txt AC 4 ms 2688 KB
subtask1_03.txt AC 695 ms 15816 KB
subtask1_04.txt AC 685 ms 15884 KB
subtask1_05.txt AC 687 ms 15596 KB
subtask1_06.txt AC 145 ms 22708 KB
subtask1_07.txt AC 305 ms 10444 KB
subtask1_08.txt AC 305 ms 10704 KB
subtask1_09.txt AC 617 ms 11108 KB
subtask1_10.txt AC 621 ms 11140 KB
subtask1_11.txt AC 4 ms 2688 KB
subtask1_12.txt AC 4 ms 2688 KB
subtask1_13.txt AC 480 ms 10280 KB
subtask1_14.txt AC 488 ms 10632 KB
subtask1_15.txt AC 45 ms 3752 KB
subtask1_16.txt AC 46 ms 3728 KB
subtask1_17.txt AC 46 ms 3776 KB
subtask1_18.txt AC 45 ms 3828 KB
subtask1_19.txt AC 46 ms 3808 KB
subtask1_20.txt AC 45 ms 3792 KB
subtask1_21.txt AC 47 ms 3760 KB
subtask1_22.txt AC 46 ms 3744 KB
subtask1_23.txt AC 46 ms 3812 KB
subtask1_24.txt AC 47 ms 3728 KB