Submission #311775

#TimeUsernameProblemLanguageResultExecution timeMemory
311775YJUMaking Friends on Joitter is Fun (JOI20_joitter2)C++14
0 / 100
7 ms9728 KiB
#include<bits/stdc++.h> #pragma GCC optimize("unroll-loops,no-stack-protector") using namespace std; typedef long long ll; typedef long double ld; typedef pair<ll,ll> pll; const ll MOD=1e9+7; const ll MOD2=998244353; const ll N=2e5+5; const ld pi=3.14159265359; const ll INF=(1LL<<60); #define SQ(i) ((i)*(i)) #define REP(i,n) for(ll i=0;i<n;i++) #define REP1(i,n) for(ll i=1;i<=n;i++) #define pb push_back #define mp make_pair #define X first #define Y second #define setp setprecision #define lwb lower_bound #define SZ(_a) (ll)_a.size() ll n,m,ans,x,y,dir[N],sz[N]; map<pll,ll> vis; set<ll> in[N]; ll f(ll id){return (id==dir[id]?id:dir[id]=f(dir[id]));} void merge(ll a,ll b){ a=f(a);b=f(b); if(a==b)return ; if(SZ(in[a])>SZ(in[b]))swap(a,b); ans-=sz[a]*SZ(in[a])+sz[b]*SZ(in[b]); sz[b]+=sz[a];sz[a]=0;dir[a]=b; while(SZ(in[a])){ ll tmp=*in[a].begin(); in[a].erase(in[a].begin()); in[b].insert(tmp); } ans+=SZ(in[b])*sz[b]; } int main(){ ios_base::sync_with_stdio(0);cin.tie(0); cin>>n>>m; //pre REP1(i,n)dir[i]=i,sz[i]=1; while(m--){ cin>>x>>y; vis[mp(x,y)]=1; if(vis[mp(y,x)]){ merge(x,y); }else{ y=f(y); if(in[y].find(x)==in[y].end()){ ans+=sz[y]; in[y].insert(x); } } cout<<ans<<"\n"; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...