Submission #1265405

#TimeUsernameProblemLanguageResultExecution timeMemory
1265405rajarshi_basu조이터에서 친구를 만드는건 재밌어 (JOI20_joitter2)C++20
0 / 100
0 ms320 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; struct DSU { int n; vector<int> p; vector<int> sz; DSU(int n = 0): n(n), p(n+1), sz(n+1,1) { iota(p.begin(), p.end(), 0); } int find(int x){ return p[x]==x ? x : p[x]=find(p[x]); } // merge b into a (caller ensures a != b and a is new root) void set_parent(int b, int a){ p[b] = a; sz[a] += sz[b]; } }; int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); int N, M; if(!(cin >> N >> M)) return 0; DSU dsu(N); // node-level outgoing edges for mutual detection vector<unordered_set<int>> g(N+1); for(int i=1;i<=N;i++) g[i].reserve(1); // component-level adjacency sets (store roots) vector<unordered_set<int>> out(N+1), in(N+1); for(int i=1;i<=N;i++){ out[i].reserve(1); in[i].reserve(1); } // sizes available from dsu.sz // answer maintained as: // ans = sum over comps size[c]*(size[c]-1) + sum over directed comp edges a->b of size[a]*size[b] ll ans = 0; auto safe_find = [&](int x){ return dsu.find(x); }; // helper to add an inter-component directed edge ra -> rb (roots) auto add_comp_edge = [&](int ra, int rb){ if(ra == rb) return; // insert if not exists if(out[ra].insert(rb).second){ in[rb].insert(ra); ans += 1LL * dsu.sz[ra] * dsu.sz[rb]; } }; // unite components a and b (by node indices). We'll merge smaller into larger. function<void(int,int)> unite = [&](int u, int v){ int a = dsu.find(u), b = dsu.find(v); if(a == b) return; // ensure a is larger if(dsu.sz[a] < dsu.sz[b]) swap(a,b); // subtract old internal contributions ans -= 1LL * dsu.sz[a] * (dsu.sz[a] - 1); ans -= 1LL * dsu.sz[b] * (dsu.sz[b] - 1); // move out-edges of b // iterate over a snapshot to allow safe modification vector<int> tmp_out; tmp_out.reserve(out[b].size()); for(int t : out[b]) tmp_out.push_back(t); for(int t0 : tmp_out){ int t = dsu.find(t0); // remove b from in[t] auto it_in = in[t].find(b); if(it_in != in[t].end()) in[t].erase(it_in); if(t == a){ // previously contributed sz[b]*sz[a], now internal -> remove that contribution ans -= 1LL * dsu.sz[b] * dsu.sz[a]; // do not add any out-edge } else { // if a already has edge to t -> no net change in cross-sum if(out[a].find(t) == out[a].end()){ // create new edge a->t out[a].insert(t); in[t].insert(a); // previously contribution was sz[b]*sz[t]; now it's (sz[a]+sz[b])*sz[t] // increase by sz[a]*sz[t] ans += 1LL * dsu.sz[a] * dsu.sz[t]; } else { // a already had edge to t; previous contributions (sz[a]*sz[t] + sz[b]*sz[t]) remain equal to (sz[a]+sz[b])*sz[t] // no change needed } } // erase entry from out[b] (we will clear afterwards) } out[b].clear(); // move in-edges of b vector<int> tmp_in; tmp_in.reserve(in[b].size()); for(int s : in[b]) tmp_in.push_back(s); for(int s0 : tmp_in){ int s = dsu.find(s0); // remove b from out[s] auto it_outs = out[s].find(b); if(it_outs != out[s].end()) out[s].erase(it_outs); if(s == a){ // previously contributed sz[a]*sz[b], now internal -> remove that contribution ans -= 1LL * dsu.sz[a] * dsu.sz[b]; } else { // if s already has edge to a -> no net change if(out[s].find(a) == out[s].end()){ out[s].insert(a); in[a].insert(s); // previously contribution sz[s]*sz[b], now becomes sz[s]* (sz[a]+sz[b]) so increase by sz[s]*sz[a] ans += 1LL * dsu.sz[s] * dsu.sz[a]; } else { // already had edge s->a, no change } } // erase entry from in[b] (we will clear afterwards) } in[b].clear(); // set parent and update size dsu.set_parent(b, a); // add new internal contribution ans += 1LL * dsu.sz[a] * (dsu.sz[a] - 1); }; for(int i=0;i<M;i++){ int A,B; cin >> A >> B; // add node-level edge A -> B g[A].insert(B); int ra = safe_find(A), rb = safe_find(B); // add component-level directed edge if inter-component if(ra != rb){ add_comp_edge(ra, rb); } // if mutual, unite components of A and B if(g[B].find(A) != g[B].end()){ unite(A, B); } cout << ans << '\n'; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...