Submission #551953

#TimeUsernameProblemLanguageResultExecution timeMemory
551953i_am_noobMaking Friends on Joitter is Fun (JOI20_joitter2)C++17
100 / 100
1113 ms87904 KiB
#include <bits/stdc++.h> using namespace std; #pragma GCC optimize("Ofast,unroll-loops") #define ll long long #define int ll #define ull unsigned ll #define ld long double #define rep(a) rep1(i,a) #define rep1(i,a) rep2(i,0,a) #define rep2(i,b,a) for(int i=(b); i<((int)(a)); i++) #define rep3(i,b,a) for(int i=(b); i>=((int)(a)); i--) #define chkmin(a,b) (a=min(a,b)) #define chkmax(a,b) (a=max(a,b)) #define all(a) a.begin(),a.end() #define pii pair<int,int> #define pb push_back //#define inf 1010000000 #define inf 4000000000000000000 #define eps 1e-9 #define sz(a) ((int)a.size()) #define pow2(x) (1ll<<(x)) #define ceiling(a,b) (((a)+(b)-1)/(b)) #define print0(a) cout << (a) << ' ' #define ykh mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()) #ifdef i_am_noob #define bug(...) cerr << "#" << __LINE__ << ' ' << #__VA_ARGS__ << "- ", _do(__VA_ARGS__) template<typename T> void _do(T && x) {cerr << x << endl;} template<typename T, typename ...S> void _do(T && x, S&&...y) {cerr << x << ", "; _do(y...);} #else #define bug(...) 777771449 #endif const int mod=1000000007; const int maxn=100005,maxm=26,maxk=7777714; //i_am_noob int n,m,res=0; int par[maxn]; vector<vector<int>> has(maxn); unordered_set<int> from[maxn],to[maxn],from2[maxn]; int Find(int x){return x==par[x]?x:par[x]=Find(par[x]);} void orzck(){ cin >> n >> m; rep(n) par[i]=i,has[i].pb(i); rep1(_,m){ int u,v; cin >> u >> v; u--,v--; if(Find(u)==Find(v)){ cout << res << "\n"; continue; } res-=sz(has[Find(v)])*sz(from2[Find(v)]); from[Find(v)].insert(Find(u)); to[Find(u)].insert(Find(v)); from2[Find(v)].insert(u); res+=sz(has[Find(v)])*sz(from2[Find(v)]); u=Find(u),v=Find(v); if((!to[u].count(v))||(!to[v].count(u))){ cout << res << "\n"; continue; } queue<int> q; while(1){ res-=sz(has[u])*sz(from2[u]); res-=sz(has[v])*sz(from2[v]); res-=sz(has[u])*(sz(has[u])-1); res-=sz(has[v])*(sz(has[v])-1); if(sz(has[u])<sz(has[v])) swap(u,v); for(auto i: has[v]) from2[u].erase(i); vector<int> tmp; for(auto i: from2[v]) if(Find(i)==u) tmp.pb(i); for(auto i: tmp) from2[v].erase(i); from[u].erase(v),to[u].erase(v); from[v].erase(u),to[v].erase(u); for(auto i: from[v]) to[i].erase(v),to[i].insert(u); for(auto i: to[v]) from[i].erase(v),from[i].insert(u); for(auto i: from[v]){ if(to[u].count(i)) q.push(i); else from[u].insert(i); } for(auto i: to[v]){ if(from[u].count(i)) q.push(i); else to[u].insert(i); } for(auto i: has[v]) has[u].pb(i); for(auto i: from2[v]) from2[u].insert(i); par[v]=u; res+=sz(has[u])*sz(from2[u]); res+=sz(has[u])*(sz(has[u])-1); v=-1; while(1){ if(q.empty()) break; v=q.front(); q.pop(); if(v==par[v]) break; else v=-1; } if(v==-1) break; } cout << res << "\n"; } } signed main(){ ios_base::sync_with_stdio(0),cin.tie(0); orzck(); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...