Submission #1129750

#	Time	Username	Problem	Language	Result	Execution time	Memory
1129750		PieArmy	Making Friends on Joitter is Fun (JOI20_joitter2)	C++20	100 / 100	749 ms	69368 KiB

joitter2

typedef long long ll;
ll pie(ll army){return (1ll<<army);}
#include <bits/stdc++.h>
#define fr first
#define sc second
#define pb push_back
#define endl '\n'
#define mid ((left+right)>>1)
const ll inf=2000000000000000005;
const int sonsuz=2000000005;
using namespace std;
ll fpow(ll x,ll y,ll m=0){if(y<0){cout<<"powError";return -1;}if(m)x%=m;ll res=1;while(y>0){if(y&1)res*=x;x*=x;if(m){x%=m;res%=m;}y>>=1;}return res;}

int n,m;
set<int>gel[100001],git[100001],gel2[100001],st[100001];
int par[100001];
ll siz[100001],ans=0;
queue<pair<int,int>>v;

int get(int x){
	if(x==par[x])return x;
	return par[x]=get(par[x]);
}

void add(int a,int b){
	git[a].insert(b);
	gel[b].insert(a);
	if(git[b].find(a)!=git[b].end()){
		v.push({a,b});
	}
}

void unite(int x,int y){
	x=get(x);y=get(y);
	if(x==y)return;
	if(siz[x]+gel[x].size()+git[x].size()+gel2[x].size()<siz[y]+gel[y].size()+git[y].size()+gel2[y].size())swap(x,y);
	ans+=siz[x]*siz[y]*2ll+siz[x]*ll(gel2[y].size())+siz[y]*ll(gel2[x].size());
	for(int a:gel2[y]){
		if(get(a)==x){
			ans-=siz[y]+siz[x];
		}
		else if(gel2[x].find(a)!=gel2[x].end()){
			ans-=siz[y]+siz[x];
		}
		else gel2[x].insert(a);
	}
	for(int a:st[y]){
		if(gel2[x].find(a)!=gel2[x].end()){
			ans-=siz[y]+siz[x];
			gel2[x].erase(a);
		}
		st[x].insert(a);
	}
	for(int a:gel[y]){
		git[a].erase(y);
		if(a==x)continue;
		add(a,x);
	}
	for(int a:git[y]){
		gel[a].erase(y);
		if(a==x)continue;
		add(x,a);
	}
	st[y].clear();
	gel2[y].clear();
	gel[y].clear();
	git[y].clear();
	par[y]=x;
	siz[x]+=siz[y];
}

void code(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		siz[i]=1;
		par[i]=i;
		st[i].insert(i);
	}
	while(m--){
		int a,b;cin>>a>>b;
		b=get(b);
		if(get(a)!=b&&gel2[b].find(a)==gel2[b].end()){
			gel2[b].insert(a);
			ans+=siz[b];
			a=get(a);
			add(a,b);
		}
		while(v.size()){
			unite(v.front().fr,v.front().sc);
			v.pop();
		}
		cout<<ans<<endl;
	}
}

int main(){
	ios_base::sync_with_stdio(false);cin.tie(NULL);
	bool usaco=0;if(usaco){freopen(".in","r",stdin);freopen(".out","w",stdout);}
	int t=1;
	if(!t)cin>>t;
	while(t--){code();}
	return 0;
}

Compilation message (stderr)

joitter2.cpp: In function 'int main()':
joitter2.cpp:98:39: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   98 |         bool usaco=0;if(usaco){freopen(".in","r",stdin);freopen(".out","w",stdout);}
      |                                ~~~~~~~^~~~~~~~~~~~~~~~~
joitter2.cpp:98:64: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   98 |         bool usaco=0;if(usaco){freopen(".in","r",stdin);freopen(".out","w",stdout);}
      |                                                         ~~~~~~~^~~~~~~~~~~~~~~~~~~

• Subtask 1: 1 / 1
• Subtask 2: 16 / 16
• Subtask 3: 83 / 83