Submission #1055692

#TimeUsernameProblemLanguageResultExecution timeMemory
1055692vjudge1Making Friends on Joitter is Fun (JOI20_joitter2)C++17
0 / 100
5 ms14428 KiB
#include<bits/stdc++.h> #pragma GCC optimize("O3") #pragma GCC target("avx2") #define ll long long #define pii pair<ll,ll> #define pll pair<ll,ll> #define plx pair<ll,int> #define f first #define s second #define pb push_back #define all(x) x.begin(),x.end() #define vi vector<int> #define vl vector<ll> #define vvi vector<vi> using namespace std; const int mxn=1e5+5; set<int>g[mxn],gr[mxn],ch[mxn]; int pr[mxn]; ll sz[mxn]{0}; int get(int r){ return pr[r]==r?r:pr[r]=get(pr[r]); }vector<pii>qr;ll ans=0; void ins(int a,int b){ g[a].insert(b);gr[b].insert(a); if(g[b].count(a))qr.pb({a,b}); } void uni(int a,int b){ a=get(a),b=get(b); if(a==b)return; if(ch[a].size()+gr[a].size()+g[a].size()<ch[b].size()+g[b].size()+gr[b].size())swap(a,b); ans+=(ll)ch[a].size()*sz[b]+(ll)ch[b].size()*sz[a]; pr[b]=a;sz[a]+=sz[b]; for(auto it : ch[b]){ if(ch[a].count(it))ans-=sz[a]; else ch[a].insert(it); } for(auto it : gr[b]){ if(g[a].count(it))ins(it,a); } for(auto it : g[b]){ if(gr[a].count(it))ins(a,it); } } int main(){ ios_base::sync_with_stdio(0);cin.tie(0); int n,m;cin>>n>>m; for(int i=1;i<=n;i++)pr[i]=i,ch[i].insert(i),sz[i]=1; for(int i=1;i<=m;i++){ int a,b;cin>>a>>b;b=get(b); if(a==b||ch[b].count(a)){cout<<ans<<'\n';continue;} ch[b].insert(a);ans+=sz[b];a=get(a);ins(a,b); while(!qr.empty())uni(qr.back().f,qr.back().s),qr.pop_back(); cout<<ans<<'\n'; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...