답안 #781445

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
781445 2023-07-13T06:32:03 Z 이성호(#10012) 도로 개발 (JOI15_road_development) C++14
0 / 100
435 ms 19156 KB
#include <iostream>
#include <cmath>
#include <functional>
#include <vector>
using namespace std;
struct Query
{
    int t, a, b;
};
Query qr[300005];
struct UnionFind
{
    vector<int> par;
    UnionFind(int N)
    {
        par.resize(N+1);
        for (int i = 1; i <= N; i++) par[i] = i;
    }
    int fin(int v)
    {
        return v == par[v] ? v : (par[v] = fin(par[v]));
    }
    void uni(int u, int v)
    {
        par[fin(u)] = fin(v);
    }
    bool isuni(int u, int v)
    {
        return fin(u) == fin(v);
    }
};
struct LazySeg
{
    vector<int> tree, lazy;
    LazySeg(int N)
    {
        int sz = 1 << ((int)ceil(log2(N+1))+1);
        tree.resize(sz); lazy.resize(sz);
    }
    void propagate(int s, int e, int node)
    {
        if (lazy[node] == 0) return;
        tree[node] = e - s + 1;
        if (s != e) {
            lazy[2*node] = lazy[2*node+1] = 1;
        }
        lazy[node] = 0;
    }
    void upd(int s, int e, int node, int l, int r)
    {
        propagate(s, e, node);
        if (e < l || r < s) return;
        if (l <= s && e <= r){
            lazy[node] = 1;
            propagate(s, e, node);
            return;
        }
        upd(s, (s+e)/2, 2*node, l, r);
        upd((s+e)/2+1, e, 2*node+1, l, r);
        tree[node] = tree[2*node] + tree[2*node+1];
    }
    int query(int s, int e, int node, int l, int r)
    {
        if (e < l || r < s) return 0;
        if (l <= s && e <= r) return tree[node];
        return query(s, (s+e)/2, 2*node, l, r) + query((s+e)/2+1, e, 2*node+1, l, r);
    }
};
vector<int> adj[100005];
vector<int> g[100005];
int in[100005], out[100005], sz[100005], par[100005], dep[100005], nxt[100005];
int main()
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int N, Q; cin >> N >> Q;
    for (int i = 0; i < Q; i++) {
        cin >> qr[i].t >> qr[i].a >> qr[i].b;
    }
    UnionFind uf(N);
    for (int i = 0; i < Q; i++) {
        if (qr[i].t == 1) {
            if (!uf.isuni(qr[i].a, qr[i].b)) {
                adj[qr[i].a].push_back(qr[i].b);
                adj[qr[i].b].push_back(qr[i].a);
                uf.uni(qr[i].a, qr[i].b);
            }
        }
    }
    for (int i = 2; i <= N; i++) {
        if (!uf.isuni(1, i)) {
            uf.uni(1, i);
            adj[1].push_back(i);
            adj[i].push_back(1);
        }
    }
    LazySeg seg(N);
    function<void(int, int)> dfs_sz = [&](int v, int p)
    {
        dep[v] = dep[p] + 1;
        par[v] = p;
        sz[v] = 1;
        for (int i:adj[v]) {
            if (i != p) {
                g[v].push_back(i);
                dfs_sz(i, v);
                if (sz[g[v][0]] < sz[i]) {
                    swap(g[v][0], g[v].back());
                }
                sz[v] += sz[i];
            }
        }
    };
    int ord = 0;
    function<void(int)> dfs_hld = [&](int v)
    {
        in[v] = ord++;
        for (int i:g[v]) {
            nxt[i] = g[v][0] == i ? nxt[v] : i;
            dfs_hld(i);
        }
        out[v] = ord;
    };
    function<int(int, int)> lca = [&](int u, int v)
    {
        while (nxt[u] != nxt[v]) {
            if (dep[nxt[u]] < dep[nxt[v]]) swap(u, v);
            u = par[nxt[u]];
        }
        return dep[u] < dep[v] ? u : v;
    };
    function<void(int, int)> upd = [&](int u, int v)
    {
        int w = lca(u, v);
        while (1) {
            if (nxt[u] != nxt[w]) {
                seg.upd(0, N-1, 1, in[nxt[u]], in[u]);
                u = par[nxt[u]];
            }
            else {
                seg.upd(0, N-1, 1, in[w]+1, in[u]);
                break;
            }
        }
        while (1) {
            if (nxt[v] != nxt[w]) {
                seg.upd(0, N-1, 1, in[nxt[v]], in[v]);
                v = par[nxt[v]];
            }
            else {
                seg.upd(0, N-1, 1, in[w]+1, in[v]);
                break;
            }
        }
    };
    function<int(int, int)> query = [&](int u, int v)
    {
        int ans = 0;
        int w = lca(u, v);
        while (1) {
            if (nxt[u] != nxt[w]) {
                ans += seg.query(0, N-1, 1, in[nxt[u]], in[u]);
                u = par[nxt[u]];
            }
            else {
                ans += seg.query(0, N-1, 1, in[w]+1, in[u]);
                break;
            }
        }
        while (1) {
            if (nxt[v] != nxt[w]) {
                ans += seg.query(0, N-1, 1, in[nxt[v]], in[v]);
                v = par[nxt[v]];
            }
            else {
                ans += seg.query(0, N-1, 1, in[w]+1, in[v]);
                break;
            }
        }
        return ans;
    };
    function<int(int, int)> dis = [&](int u, int v)
    {
        int w = lca(u, v);
        return dep[u] + dep[v] - 2 * dep[w];
    };
    dfs_sz(1, 0);
    dfs_hld(1);
    UnionFind uf2(N);
    for (int i = 0; i < Q; i++) {
        if (qr[i].t == 1) {
            if (uf2.isuni(qr[i].a, qr[i].b)) {
                upd(qr[i].a, qr[i].b);
            }
            else {
                uf2.uni(qr[i].a, qr[i].b);
            }
        }
        else {
            if (uf2.isuni(qr[i].a, qr[i].b)) {
                cout << dis(qr[i].a, qr[i].b) - query(qr[i].a, qr[i].b) << '\n';
            }
            else {
                cout << -1 << '\n';
            }
        }
    }
}
# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 5204 KB Output is correct
2 Incorrect 5 ms 5204 KB Output isn't correct
3 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 195 ms 18364 KB Output is correct
2 Incorrect 435 ms 19156 KB Output isn't correct
3 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 205 ms 18376 KB Output is correct
2 Incorrect 306 ms 19148 KB Output isn't correct
3 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 133 ms 17016 KB Output is correct
2 Incorrect 292 ms 17836 KB Output isn't correct
3 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 5204 KB Output is correct
2 Incorrect 5 ms 5204 KB Output isn't correct
3 Halted 0 ms 0 KB -