Instantly share code, notes, and snippets.

# yurahuna/aoj1330.cpp Created Dec 23, 2016

 #include using namespace std; #define int long long // <-----!!!!!!!!!!!!!!!!!!! #define rep(i,n) for (int i=0;i<(n);i++) #define rep2(i,a,b) for (int i=(a);i<(b);i++) #define rrep(i,n) for (int i=(n)-1;i>=0;i--) #define rrep2(i,a,b) for (int i=(a)-1;i>=b;i--) #define chmin(a,b) (a)=min((a),(b)); #define chmax(a,b) (a)=max((a),(b)); #define all(a) (a).begin(),(a).end() #define rall(a) (a).rbegin(),(a).rend() #define printV(v) cout<<(#v)<<":";for(auto(x):(v)){cout<<" "<<(x);}cout< inline void output(const First& first, const Rest&... rest) { cerr << first << " "; output(rest...); } using ll = long long; using Pii = pair; using vi = vector; using vvi = vector; using vvvi = vector; const int inf = 2e9; const int mod = 1e9 + 7; struct edge { int to, cost; edge(){} edge(int _to, int _cost) : to(_to), cost(_cost) {} }; using Graph = vector>; class LCA { private: static const int MAX_LOG = 20; const int n; Graph G; vector> par; vector depth; vector cost; public: void bfs() { // v, p, d, c using State = tuple; queue que; que.push(State(0, -1, 0, 0)); while (!que.empty()) { int v, p, d, c; tie(v, p, d, c) = que.front(); que.pop(); par[0][v] = p; depth[v] = d; cost[v] = c; for (auto e : G[v]) { if (e.to != p) { que.push(State(e.to, v, d + 1, c + e.cost)); } } } } LCA(int _n) : n(_n), G(_n), par(MAX_LOG, vector(_n)), depth(_n), cost(_n) {} void addEdge(int a, int b, int c) { G[a].emplace_back(b, c); G[b].emplace_back(a, -c); } void init(bool debug = false) { bfs(); rep(i, MAX_LOG - 1) { rep(j, n) { if (par[i][j] == -1) { par[i + 1][j] = -1; } else { par[i + 1][j] = par[i][par[i][j]]; } } } } int lca(int a, int b) { if (depth[a] > depth[b]) { swap(a, b); } rep(i, MAX_LOG) { if ((depth[b] - depth[a]) >> i & 1) { b = par[i][b]; } } if (a == b) return a; rrep(i, MAX_LOG) { if (par[i][a] != par[i][b]) { a = par[i][a]; b = par[i][b]; } } return par[0][a]; } int query(int a, int b) { int v = lca(a, b); return - (cost[a] - cost[v]) + cost[b] - cost[v]; } }; class UnionFind { private: const int n; vector uni; public: UnionFind(int _n) : n(_n), uni(_n, -1) {} int root(int x) { if (uni[x] < 0) return x; return uni[x] = root(uni[x]); } bool same(int x, int y) { return root(x) == root(y); } bool unite(int x, int y) { x = root(x); y = root(y); if (x == y) return false; if (uni[x] > uni[y]) swap(x, y); uni[x] += uni[y]; uni[y] = x; return true; } int getSize(int x) { return -uni[root(x)]; } void print() { for (auto x : uni) cout << x << " "; cout << endl; } }; struct Query { char t; int a, b; Query(){} Query(char t, int a, int b) : t(t), a(a), b(b) {} void disp() { output(t, a, b); } }; signed main() { std::ios::sync_with_stdio(false); std::cin.tie(0); int n, m; while (cin >> n >> m, n) { // s = 0: super root // v = 1, 2, ...: items const int s = 0; LCA lca(n + 1); UnionFind uf(n + 1); vector queries; rep(i, m) { char t; int a, b; cin >> t >> a >> b; queries.emplace_back(t, a, b); if (t == '!') { int c; cin >> c; if (uf.unite(a, b)) { lca.addEdge(a, b, c); } } } rep2(i, 1, n + 1) { // connect s and the one of groups if (uf.unite(s, i)) { lca.addEdge(s, i, 0); } } lca.init(); { UnionFind uf(n + 1); for (const auto& q : queries) { if (q.t == '!') { uf.unite(q.a, q.b); } else { if (uf.same(q.a, q.b)) { cout << lca.query(q.a, q.b) << endl; } else { cout << "UNKNOWN" << endl; } } } } } }