Submission #1216990

#TimeUsernameProblemLanguageResultExecution timeMemory
1216990vaneaMaking Friends on Joitter is Fun (JOI20_joitter2)C++20
0 / 100
621 ms1114112 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; const int mxN = 1e5+10; set<int> adj[mxN], rev_adj[mxN], child[mxN]; int p[mxN]; ll ans = 0; queue<pair<int, int>> to_merge; int get(int x) { return p[x] < 0 ? x : p[x] = get(p[x]); } void add(int a, int b) { adj[a].insert(b); rev_adj[b].insert(a); if(adj[b].count(a)) { to_merge.push({a, b}); } } int dsu_size(int a) { return child[a].size() + adj[a].size() + rev_adj[a].size(); } void uni(int a, int b) { if(a == b) return ; if(dsu_size(a) < dsu_size(b)) swap(a, b); ans += (ll)(-p[b]) * child[a].size() + (ll)(-p[a]) * child[b].size(); p[a] += p[b]; p[b] = a; for(auto it : child[b]) { if(child[a].count(it)) ans += p[a]; else child[a].insert(it); } child[b].clear(); adj[a].erase(b), rev_adj[a].erase(b); adj[b].erase(a), rev_adj[b].erase(a); for(auto it : adj[b]) { rev_adj[it].erase(b); add(a, it); } for(auto it : rev_adj[b]) { adj[it].erase(b); add(it, a); } adj[b].clear(); rev_adj[b].clear(); } int main() { ios_base::sync_with_stdio(0); cin.tie(0); int n, m; cin >> n >> m; for(int i = 1; i <= n; i++) { p[i] = -1; child[i].insert(i); } while(m--) { int a, b; cin >> a >> b; b = get(b); if(get(a) != b && !child[b].count(a)) { child[b].insert(a); ans += (ll)(-p[b]); a = get(a); add(a, b); while(!to_merge.empty()) { tie(a, b) = to_merge.front(); to_merge.pop(); uni(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...