verify/Datastructure_potential_dsu.test.cpp

View this file on GitHub
Last update: 2025-01-10 00:00:54+09:00
Problem: https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1330

Depends on

Code

#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1330"
#include "../Utility/template.hpp"
#include "../Datastructure/potential_dsu.hpp"

int main() {
    int N, M;
    while(cin >> N >> M) {
        if(N==0) break;
        potential_dsu<ll> uf(N, 1);
        rep(i, 0, M) {
            char c;
            cin >> c;
            int a, b, w;
            if(c == '!') {
                cin >> a >> b >> w;
                --a, --b;
                uf.merge(a, b, w);
            }
            else {
                cin >> a >> b;
                --a, --b;
                if(!uf.same(a, b)) cout << "UNKNOWN" << endl;
                else cout << uf.diff(a, b) << endl;
            }
        }
    }
    
}

#line 1 "verify/Datastructure_potential_dsu.test.cpp"
#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1330"
#line 1 "Utility/template.hpp"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, s, t) for (ll i = s; i < (ll)(t); i++)
#define rrep(i, s, t) for (ll i = (ll)(t) - 1; i >= (ll)(s); i--)
#define all(x) begin(x), end(x)

#define TT template <typename T>
TT using vec = vector<T>;
template <class T1, class T2> bool chmin(T1 &x, T2 y) {
    return x > y ? (x = y, true) : false;
}
template <class T1, class T2> bool chmax(T1 &x, T2 y) {
    return x < y ? (x = y, true) : false;
}
struct io_setup {
    io_setup() {
        ios::sync_with_stdio(false);
        std::cin.tie(nullptr);
        cout << fixed << setprecision(15);
    }
} io_setup;

/*
@brief verify用テンプレート
*/
#line 1 "Datastructure/potential_dsu.hpp"
TT struct potential_dsu {
    using vi = vec<int>;
    using vvi = vec<vi>;
    vi par, sz, es;
    vec<T> h;
    int cc;
    int root;

    potential_dsu(int n, int ROOT) : root(ROOT) {
        par = vi(n);
        sz = vi(n, 1);
        es = vi(n, 0);
        cc = n;
        iota(all(par), 0);

        h = vec<T>(n, 0);
    }

    int leader(int u) {
        if(par[u] != u) {
            int r = leader(par[u]);
            h[u] += h[par[u]];
            return par[u] = r;
        }
        return u;
    }

    bool same(int a, int b) {
        return leader(a) == leader(b);
    }

    bool merge(int s, int t, T w) {// h[t] = h[s] + w 或いは s -> tに重みwの辺　  
        w += weight(s), w -= weight(t);
        s = leader(s), t = leader(t);
        if(s == t) {
            es[s]++;
            return false;
        }

        if(sz[s] < sz[t] && s != root) {
            swap(s, t);
            w *= -1;
        }

        cc--;
        par[t] = s;
        sz[s] += sz[t];
        es[s] += es[t] + 1;

        h[t] = w;
        return true;
        
    }

    T weight(int v) {//根から見た vの値  p[根]は0。
        leader(v);
        return h[v];
    }

    T diff(int s, int t) {//sから見た tの値
        return weight(t) - weight(s);
    }

};

/*
@brief potential dsu
*/

#line 4 "verify/Datastructure_potential_dsu.test.cpp"

int main() {
    int N, M;
    while(cin >> N >> M) {
        if(N==0) break;
        potential_dsu<ll> uf(N, 1);
        rep(i, 0, M) {
            char c;
            cin >> c;
            int a, b, w;
            if(c == '!') {
                cin >> a >> b >> w;
                --a, --b;
                uf.merge(a, b, w);
            }
            else {
                cin >> a >> b;
                --a, --b;
                if(!uf.same(a, b)) cout << "UNKNOWN" << endl;
                else cout << uf.diff(a, b) << endl;
            }
        }
    }
    
}