Submission #939391

#TimeUsernameProblemLanguageResultExecution timeMemory
939391WonderfulWhaleMaking Friends on Joitter is Fun (JOI20_joitter2)C++17
1 / 100
5045 ms17664 KiB
#include<bits/stdc++.h> using namespace std; #define int int64_t #define pb push_back #define pii pair<int, int> #define st first #define nd second #define sz(x) (int)(x).size() #define all(x) (x).begin(), (x).end() const int MAXN = 100'009; int cnt[MAXN]; int p[MAXN]; int sz[MAXN]; set<int> in[MAXN]; set<int> out[MAXN]; int ans; int Find(int x) { return x==p[x]?x:p[x]=Find(p[x]); } void Union(int a, int b) { a = Find(a); b = Find(b); //cout << "Union: " << a << " " << b << "\n"; if(a==b) return; vector<int> union_queue; if(sz(out[a])+sz(in[a])<sz(out[b])+sz(in[b])) swap(a, b); for(int x:out[b]) { //cerr << "trying: "<< x << "\n"; if(in[a].count(x)) { //cerr << "found: " << x << "\n"; union_queue.pb(x); } //cerr << "adding: " << x << "\n"; out[a].insert(x); in[x].erase(b); in[x].insert(a); } out[b].clear(); //if(sz(in[a])<sz(in[b])) swap(a, b); for(int x:in[b]) { //cerr << "trying: "<< x << "\n"; if(out[a].count(x)) { //cerr << "found: " << x << "\n"; union_queue.pb(x); } in[a].insert(x); //cerr << "changin: "<< x << " from: " << b << " to "<< a << "\n"; out[x].erase(b); out[x].insert(a); } in[b].clear(); p[b] = a; ans -= sz[a]*(sz[a]-1); ans -= sz[b]*(sz[b]-1); sz[a] += sz[b]; ans += sz[a]*(sz[a]-1); for(int x:union_queue) { Union(a, x); } } set<pii> S; set<int> used[MAXN]; int32_t main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int n, m; cin >> n >> m; iota(p, p+n+1, 0); fill(sz, sz+n+1, 1); for(int i=0;i<m;i++) { int a, b; cin >> a >> b; S.insert({a, b}); int A = Find(a); int B = Find(b); if(A==B) goto skip; out[A].insert(B); in[B].insert(A); if(in[A].count(B)) { Union(A, B); } skip: int cnt = 0; for(int i=1;i<=n;i++) { used[i].clear(); } for(pii x:S) { if(Find(x.st)==Find(x.nd)) continue; if(used[x.st].count(Find(x.nd))) continue; cnt += sz[Find(x.nd)]; used[x.st].insert(Find(x.nd)); } //cerr << ans << " " << cnt << "\n"; cout << ans+cnt << "\n"; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...