oj.uz

Submission #245450

# Submission time Handle Problem Language Result Execution time Memory
245450 2020-07-06T13:19:43 Z TadijaSebez Making Friends on Joitter is Fun (JOI20_joitter2) C++11
0 / 100
 16 ms 19200 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
const int N=100050;
set<int> in[N],all[N],E[N],R[N];
int my[N];
ll ans;
ll Calc(int cmp){
	return (ll)all[cmp].size()*((int)all[cmp].size()-1)+(ll)in[cmp].size()*all[cmp].size();
}
void Del(int cmp){
	ans-=Calc(cmp);
}
void Add(int cmp){
	ans+=Calc(cmp);
}
int Mrg(int A,int B){
	if(all[A].empty())return B;
	if(all[B].empty())return A;
	//printf("Mrg %i %i\n",A,B);
	Del(A);Del(B);
	E[B].erase(A);
	R[A].erase(B);
	E[A].erase(B);
	R[B].erase(A);
	if(all[A].size()+in[A].size()+E[A].size()+R[A].size()>all[B].size()+in[B].size()+E[B].size()+R[B].size())swap(A,B);
	for(int x:all[A]){
		if(in[B].count(x))in[B].erase(x);
		all[B].insert(x);
		my[x]=B;
	}
	all[A].clear();
	for(int x:in[A]){
		if(!all[B].count(x))in[B].insert(x);
	}
	in[A].clear();
	vector<int> nxt;
	for(int x:E[A]){
		if(R[B].count(x))nxt.pb(x);
		R[x].erase(A);
		if(!E[B].count(x)){
			E[B].insert(x);
			R[x].insert(B);
		}
	}
	E[A].clear();
	for(int x:R[A]){
		if(E[B].count(x))nxt.pb(x);
		E[x].erase(A);
		if(!R[B].count(x)){
			R[B].insert(x);
			E[x].insert(B);
		}
	}
	R[A].clear();
	Add(B);
	sort(nxt.begin(),nxt.end());
	nxt.erase(unique(nxt.begin(),nxt.end()),nxt.end());
	//for(int x:nxt){
	//	if(B!=x)B=Mrg(B,x);
	//}
	return B;
}
int main(){
	int n,m;scanf("%i %i",&n,&m);
	for(int i=1;i<=n;i++)all[i].insert(i),my[i]=i;
	for(int i=1;i<=m;i++){
		int u,v;scanf("%i %i",&u,&v);
		int A=my[u],B=my[v];
		if(A!=B){
			Del(B);
			in[B].insert(u);
			E[A].insert(B);
			R[B].insert(A);
			Add(B);
			for(int i=1;i<=n;i++){
				if(E[i].count(my[u])&&E[my[u]].count(i)){
					Mrg(i,my[u]);
				}
				if(E[i].count(my[v])&&E[my[v]].count(i)){
					Mrg(i,my[v]);
				}
			}
		}
		printf("%lld\n",ans);
	}
	return 0;
}

Compilation message

joitter2.cpp: In function 'int main()':
joitter2.cpp:66:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  int n,m;scanf("%i %i",&n,&m);
          ~~~~~^~~~~~~~~~~~~~~
joitter2.cpp:69:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int u,v;scanf("%i %i",&u,&v);
           ~~~~~^~~~~~~~~~~~~~~

Subtask #1
0 / 1.0

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

Subtask #2
0 / 16.0

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

Subtask #3
0 / 83.0

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