Submission #1108296

#TimeUsernameProblemLanguageResultExecution timeMemory
1108296sitablechairMaking Friends on Joitter is Fun (JOI20_joitter2)C++17
0 / 100
2 ms9808 KiB
#include <bits/stdc++.h> #define ll long long #define ldb long double #define endl '\n' #define For(i,l,r) for(int i=l;i<=r;i++) #define ForD(i,r,l) for(int i=r;i>=l;i--) #define REP(i,l,r) For(i,l,r-1) #define PER(i,r,l) ForD(i,r-1,l) #define ff first #define ss second #define pb push_back #define all(x) x.begin(),x.end() #define All(x,n) x+1,x+1+n #define Alll(x,n) x,x+n #define sz(x) (signed)x.size() #define unq(x) x.resize(unique(all(x))-x.begin()) #define mpa make_pair #ifdef NCGM #include"debug.h" #else #define debug(...) "fr"; #endif using namespace std; const int N=1e5+3; int f[N],n,m; set<int> st[N],st1[N]; map<pair<int,int>,bool> sus; ll ans=0; int find_set(int u) { return (f[u]<0?u:f[u]=find_set(f[u])); } void unite(int u,int v) { int a=find_set(u),b=find_set(v); if (a==b) return; if (st[a]<st[b]) swap(a,b); ans+=1LL*sz(st1[a])*f[a]; ans+=1LL*sz(st1[b])*f[b]; ans-=1LL*f[a]*(f[a]-1); ans-=1LL*f[b]*(f[b]-1); for(auto el: st[b]) { if (st1[a].find(el)!=st1[a].end()) st1[a].erase(el); st[a].insert(el); } st[b].clear(); for(auto el: st1[b]) if (st[a].find(el)==st[a].end()) st1[a].insert(el); st1[b].clear(); f[a]+=f[b]; f[b]=a; ans+=1LL*f[a]*(f[a]-1); ans-=1LL*f[a]*sz(st1[a]); } int main() { cin.tie(0)->sync_with_stdio(0); cin >> n >> m; For(i,1,n) { f[i]=-1; st[i].insert(i); } For(i,1,m) { int u,v; cin >> u >> v; if (sus[{v,u}]) unite(u,v); else { if (st1[find_set(v)].find(u)==st1[find_set(v)].end()) { st1[find_set(v)].insert(u); ans++; } } sus[{u,v}]=1; cout << ans << endl; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...