XOR回廊 (KUPC 2012)

http://kupc2012.contest.atcoder.jp/tasks/kupc2012_11#

問題

略

解法

解説参照

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <iostream>
#include <math.h>
#include <assert.h>
#include <vector>
#include <queue>
#include <string>
#include <map>
#include <set>

using namespace std;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
static const double EPS = 1e-9;
static const double PI = acos(-1.0);

#define REP(i, n) for (int i = 0; i < (int)(n); i++)
#define FOR(i, s, n) for (int i = (s); i < (int)(n); i++)
#define FOREQ(i, s, n) for (int i = (s); i <= (int)(n); i++)
#define FORIT(it, c) for (__typeof((c).begin())it = (c).begin(); it != (c).end(); it++)
#define MEMSET(v, h) memset((v), h, sizeof(v))

struct Edge {
  int src;
  int dest;
  ll cost;
  Edge() {;}
  Edge(int src, int dest, ll cost) : src(src), dest(dest), cost(cost) {;}
};

typedef vector<Edge> Edges;
typedef vector<Edges> Graph;

int n, m, q;
Graph g;
int visit[100010];
ll dist[100010];
ll base[100];

void Push(ll v) {
  int first = -1;
  for (int i = 60; i >= 0; i--) {
    if (v & (1LL << i)) {
      v ^= base[i];
      if (v & (1LL << i)) { first = max(first, i); }
    }
  }
  assert(first != -1 || v == 0);
  if (first != -1) { base[first] = v; }
}

void dfs(int from, int parent, ll cost) {
  if (visit[from] == 2) { return; }
  if (visit[from] == 1) {
    Push(cost ^ dist[from]);
    return;
  }
  visit[from] = 1;
  dist[from] = cost;
  FORIT(it, g[from]) {
    int to = it->dest;
    if (to == parent) { continue; }
    dfs(to, from, cost ^ it->cost);
  }
  visit[from] = 2;
}

int main() {
  while (scanf("%d %d %d", &n, &m, &q) > 0) {
    MEMSET(visit, 0);
    MEMSET(dist, -1);
    MEMSET(base, 0);
    g = Graph(n);
    REP(i, m) {
      int f, t;
      ll w;
      int v = scanf("%d %d %lld", &f, &t, &w);
      assert(v == 3);
      g[f].push_back(Edge(f, t, w));
      g[t].push_back(Edge(t, f, w));
    }
    dfs(0, 0, 0);
    REP(iter, q) {
      int f, t;
      int v = scanf("%d %d", &f, &t);
      assert(v == 2);
      ll ans = dist[f] ^ dist[t];
      for (int i = 60; i >= 0; i--) {
        if (!(ans & (1LL << i))) { ans ^= base[i]; }
      }
      printf("%lld\n", ans);
    }
  }
}