Create a gist now

Instantly share code, notes, and snippets.

What would you like to do?
#include <bits/stdc++.h>
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<<endl;
#define printVS(vs) cout<<(#vs)<<":"<<endl;for(auto(s):(vs)){cout<<(s)<< endl;}
#define printVV(vv) cout<<(#vv)<<":"<<endl;for(auto(v):(vv)){for(auto(x):(v)){cout<<" "<<(x);}cout<<endl;}
#define printP(p) cout<<(#p)<<(p).first<<" "<<(p).second<<endl;
#define printVP(vp) cout<<(#vp)<<":"<<endl;for(auto(p):(vp)){cout<<(p).first<<" "<<(p).second<<endl;}
inline void output(){ cerr << endl; }
template<typename First, typename... Rest>
inline void output(const First& first, const Rest&... rest) {
cerr << first << " "; output(rest...);
}
using ll = long long;
using Pii = pair<int, int>;
using vi = vector<int>;
using vvi = vector<vi>;
using vvvi = vector<vvi>;
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<vector<edge>>;
class LCA {
private:
static const int MAX_LOG = 20;
const int n;
Graph G;
vector<vector<int>> par;
vector<int> depth;
vector<int> cost;
public:
void bfs() {
// v, p, d, c
using State = tuple<int, int, int, int>;
queue<State> 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<int>(_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<int> 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<Query> 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;
}
}
}
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment