Submission #1216121

#	Time	Username	Problem	Language	Result	Execution time	Memory
1216121		duckindog	도로 개발 (JOI15_road_development)	C++20	100 / 100	176 ms	31296 KiB

road_development

#include <bits/stdc++.h>

using namespace std;

const int N = 300'000 + 10;
int n, q;
struct Edge { 
    int type, u, v;
    friend istream& operator >> (istream& is, Edge& rhs) { 
        return is >> rhs.type >> rhs.u >> rhs.v;
    }
} edge[N];

struct DSU {
    int id[N];

    void init() { 
        memset(id, -1, sizeof id);
    }
    int root(int u) { return id[u] < 0 ? u : id[u] = root(id[u]); }
    void join(int u, int v) { 
        u = root(u); v = root(v);
        if (u == v) return;
        id[u] += id[v];
        id[v] = u;
    }

    bool isCon(int u, int v) { return root(u) == root(v); }
} T, D;

vector<int> ad[N];

int f[N][17];
int st[N], ed[N], timer;
void dfs(int u, int p = -1) { 
    st[u] = ++timer;

    for (int i = 1; i <= 16; ++i)
        f[u][i] = f[f[u][i - 1]][i - 1];

    for (const auto& v : ad[u]) { 
        if (v == p) continue;
        f[v][0] = u;
        dfs(v, u);
    }

    ed[u] = timer;
}
inline bool anc(int u, int v) { return st[u] <= st[v] && ed[u] >= ed[v]; }
int lca(int u, int v) { 
    if (anc(u, v)) return u;
    if (anc(v, u)) return v;

    for (int i = 16; i >= 0; --i)
        if (!anc(f[u][i], v)) u = f[u][i];
    return f[u][0];
}

namespace BIT { 
    int bit[N];
    inline void upd(int i, int x) { 
        for (; i <= n; i += i & -i) bit[i] += x;
    }
    inline int que(int i) { 
        int ret = 0;
        for (; i; i -= i & -i) ret += bit[i];
        return ret;
    }

    inline void upd(int l, int r, int x) { 
        upd(l, x);
        upd(r + 1, -x);
    }
}

int32_t main() { 
    cin.tie(0)->sync_with_stdio(0);

    cin >> n >> q;
    for (int i = 1; i <= q; ++i) cin >> edge[i];
    
    T.init();
    for (int i = 1; i <= q; ++i) { 
        const auto& [type, u, v] = edge[i];
        if (type == 1) { 
            if (!T.isCon(u, v)) { 
                ad[u].push_back(v);
                ad[v].push_back(u);
                
                T.join(u, v);
            }
        }
    }
    
    for (int i = 1; i <= n; ++i) 
        if (!st[i]) dfs(f[i][0] = i);
    for (int i = 1; i <= n; ++i) 
        if (f[i][0] != i) BIT::upd(st[i], ed[i], 1);
    
    T.init(); D.init();
    for (int i = 1; i <= q; ++i) { 
        auto [type, u, v] = edge[i];
        if (anc(v, u)) swap(u, v);
        
        if (type == 1) { 
            if (!T.isCon(u, v)) { 
                T.join(u, v);
            } else { 
                for (int turn = 0; turn <= 1; ++turn) { 
                    for (;;) { 
                        int x = D.root(v);
                        if (anc(x, u)) break;
                        D.join(f[x][0], x);
                        BIT::upd(st[x], ed[x], -1);
                    }
                    swap(u, v);
                }
            }
        } else { 
            if (!T.isCon(u, v)) cout << -1 << "\n";
            else cout << BIT::que(st[u]) + BIT::que(st[v]) - 2 * BIT::que(st[lca(u, v)]) << "\n";
        }
    }
}

• Subtask 1: 10 / 10
• Subtask 2: 25 / 25
• Subtask 3: 25 / 25
• Subtask 4: 25 / 25
• Subtask 5: 15 / 15