oj.uz

Submission #771767

# Submission time Handle Problem Language Result Execution time Memory
771767 2023-07-03T09:07:25 Z Mohammad_Parsa Making Friends on Joitter is Fun (JOI20_joitter2) C++17
0 / 100
 6 ms 12072 KB 
/* in the name of allah */
#include<bits/stdc++.h>
using namespace std;

#define endl '\n'
#define pb push_back
#define F first
#define S second
#define mk make_pair
typedef long long ll;

const int N=1e5+7;
int n,m,a[N];
ll ans,sz[N];
vector<int>st[N];
set<pair<int,int>>v[N];
vector<int>vec[N],cev[N];

void upd(int i,int x){
	for(auto u:vec[i]){
		v[a[u]].erase(mk(a[i],i));
		if(a[u]==x || a[u]==a[i])continue;
		v[a[u]].insert(mk(x,i));
	}
	for(auto u:cev[i]){
		v[a[i]].erase(mk(a[u],u));
		if(a[u]==x || a[u]==a[i])continue;
		v[x].insert(mk(a[u],u));
	}
	a[i]=x;
}

void merge(int x,int y){
	ans-=sz[x]*v[x].size();
	ans-=sz[y]*v[y].size();
	ans-=sz[x]*(sz[x]-1);
	ans-=sz[y]*(sz[y]-1);

	if(st[x].size()<st[y].size())swap(x,y);
	for(auto i:st[y]){
		upd(i,x);
		st[x].pb(i);
	}
	sz[x]+=sz[y];
	ans+=sz[x]*(sz[x]-1);
	ans+=sz[x]*v[x].size();
}

int main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		a[i]=i;
		sz[i]=1;
		st[i].pb(i);
	}
	int u,V;
	while(m--){
		cin>>u>>V;
		vec[u].pb(V);
		cev[V].pb(u);
		int x=a[u],y=a[V];
		if(x==y){
			cout<<ans<<endl;
			continue;
		}
		if(!v[y].count(mk(x,u)))ans+=1ll*(sz[y]);
		v[y].insert(mk(x,u));

		auto it=v[x].lower_bound(mk(y,0));
		if(it!=v[x].end() && it->F==y)merge(x,y);
		
		cout<<ans<<endl;
	}
}

Subtask #1
0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11988 KB Output is correct
2 Correct 6 ms 12072 KB Output is correct
3 Incorrect 5 ms 11988 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11988 KB Output is correct
2 Correct 6 ms 12072 KB Output is correct
3 Incorrect 5 ms 11988 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 83.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11988 KB Output is correct
2 Correct 6 ms 12072 KB Output is correct
3 Incorrect 5 ms 11988 KB Output isn't correct
4 Halted 0 ms 0 KB -