Submission #216314

#	Time	Username	Problem	Language	Result	Execution time	Memory
216314		model_code	Making Friends on Joitter is Fun (JOI20_joitter2)	C++17	100 / 100	1198 ms	54520 KiB

joitter2

#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<deque>
#include<stack>
#include<string>
#include<string.h>
#include<vector>
#include<set>
#include<map>
#include<bitset>
#include<stdlib.h>
#include<cassert>
#include<time.h>
#include<bitset>
#include<numeric>
#include<unordered_set>
#include<unordered_map>
#include<complex>
using namespace std;
const long long mod=1000000007;
const long long inf=mod*mod;
const long long d2=(mod+1)/2;
const long double EPS=1e-9;
const double INF=1e+10;
const double PI=acos(-1.0);
const int C_SIZE = 3100000;
const int UF_SIZE = 3100000;
namespace{
	long long fact[C_SIZE];
	long long finv[C_SIZE];
	long long inv[C_SIZE];
	long long Comb(int a,int b){
	 	if(a<b||b<0)return 0;
	 	return fact[a]*finv[b]%mod*finv[a-b]%mod;
	}
	void init_C(int n){
		fact[0]=finv[0]=inv[1]=1;
		for(int i=2;i<n;i++){
			inv[i]=(mod-(mod/i)*inv[mod%i]%mod)%mod;
		}
		for(int i=1;i<n;i++){
			fact[i]=fact[i-1]*i%mod;
			finv[i]=finv[i-1]*inv[i]%mod;
		}
	}
	long long pw(long long a,long long b){
		if(a<0LL)return 0;
		if(b<0LL)return 0;
		long long ret=1;
		while(b){
			if(b%2)ret=ret*a%mod;
			a=a*a%mod;
			b/=2;
		}
		return ret;
	}
	long long pw_mod(long long a,long long b,long long M){
		if(a<0LL)return 0;
		if(b<0LL)return 0;
		long long ret=1;
		while(b){
			if(b%2)ret=ret*a%M;
			a=a*a%M;
			b/=2;
		}
		return ret;
	}
	int pw_mod_int(int a,int b,int M){
		if(a<0)return 0;
		if(b<0)return 0;
		int ret=1;
		while(b){
			if(b%2)ret=(long long)ret*a%M;
			a=(long long)a*a%M;
			b/=2;
		}
		return ret;
	}
	int ABS(int a){return max(a,-a);}
	long long ABS(long long a){return max(a,-a);}
	double ABS(double a){return max(a,-a);}
	int sig(double r) { return (r < -EPS) ? -1 : (r > +EPS) ? +1 : 0; }
	int UF[UF_SIZE];
	void init_UF(int n){
		for(int i=0;i<n;i++)UF[i]=-1;
	}
	int FIND(int a){
		if(UF[a]<0)return a;
		return UF[a]=FIND(UF[a]);
	}
	void UNION(int a,int b){
		a=FIND(a);b=FIND(b);if(a==b)return;
		// if(UF[a]>UF[b])swap(a,b);
		UF[a]+=UF[b];UF[b]=a;
	}
}
// �볝걪�뗣굢渶③썓�쀣굧
set<pair<int,int> >IN[210000];
set<pair<int,int> >OUT[210000];

int par[210000];
long long ret=0;
void ae(int A,int B,int a,int b){
	OUT[A].insert(make_pair(B,a));
	IN[B].insert(make_pair(A,a));
	// OUTM[A][B]++;
	// INM[B][A]++;
	ret+=-UF[B];
	queue<pair<int,int> >Q;
	set<pair<int,int> > ::iterator it=OUT[B].lower_bound(make_pair(A,0));
	if(it!=OUT[B].end()&&it->first==A){
		Q.push(make_pair(A,B));
	}
	while(Q.size()){
		int l=FIND(Q.front().first);
		int r=FIND(Q.front().second);
		// printf("%d %d %lld\n",l,r,ret);
		Q.pop();
		if(FIND(l)==FIND(r))continue;
		int sl=-UF[l];
		int sr=-UF[r];
		it=OUT[r].lower_bound(make_pair(l,0));
		vector<pair<int,int> >del;
		while(it!=OUT[r].end()&&it->first==l){
			del.push_back(*it);
			ret-=sl;
			it++;
		}
		for(int i=0;i<del.size();i++)OUT[r].erase(del[i]);

		del.clear();
		it=OUT[l].lower_bound(make_pair(r,0));
		while(it!=OUT[l].end()&&it->first==r){
			ret-=sr;
			del.push_back(*it);
			it++;
		}
		for(int i=0;i<del.size();i++)OUT[l].erase(del[i]);
		del.clear();
		it=IN[l].lower_bound(make_pair(r,0));
		while(it!=IN[l].end()&&it->first==r){
			del.push_back(*it);
			it++;
		}
		for(int i=0;i<del.size();i++)IN[l].erase(del[i]);
		del.clear();
		it=IN[r].lower_bound(make_pair(l,0));
		while(it!=IN[r].end()&&it->first==l){
			del.push_back(*it);
			it++;
		}
		for(int i=0;i<del.size();i++)IN[r].erase(del[i]);
		del.clear();
		// OUTM[r][l]=0;
		// OUTM[l][r]=0;
		// INM[r][l]=0;
		// INM[l][r]=0;

		// printf("%d %d %lld\n",l,r,ret);
		ret+=(long long)sr*sl*2;
		// printf("%d %d %lld\n",l,r,ret);
		if(IN[l].size()+OUT[l].size()<IN[r].size()+OUT[r].size()){
			swap(l,r);
			swap(sl,sr);
		}
		int bap=IN[l].size();
		for(set<pair<int,int> >::iterator i=IN[r].begin();i!=IN[r].end();i++){
			pair<int,int>tmp=*i;
			// set<pair<int,int> >::iterator j=IN[l].lower_bound(make_pair(tmp.first,0));
			if(IN[l].count(tmp)){
				bap--;
			}
		}
		ret+=(long long)sr*bap;
		// printf("%d %d %d %d %d %lld\n",l,r,bap,sl,sr,ret);
		// printf("IN[%d]\n",r);
		// for(set<pair<int,int> >::iterator i=IN[r].begin();i!=IN[r].end();i++){
		// 	printf("%d %d\n",i->first,i->second);
		// }
		// printf("IN[%d]\n",l);
		// for(set<pair<int,int> >::iterator i=IN[l].begin();i!=IN[l].end();i++){
		// 	printf("%d %d\n",i->first,i->second);
		// }
		// printf("OUT[%d]\n",r);
		// for(set<pair<int,int> >::iterator i=OUT[r].begin();i!=OUT[r].end();i++){
		// 	printf("%d %d\n",i->first,i->second);
		// }
		// printf("OUT[%d]\n",l);
		// for(set<pair<int,int> >::iterator i=OUT[l].begin();i!=OUT[l].end();i++){
		// 	printf("%d %d\n",i->first,i->second);
		// }
		
		set<int>mg;
		for(set<pair<int,int> >::iterator i=IN[r].begin();i!=IN[r].end();i++){
			pair<int,int>tmp=*i;
			set<pair<int,int> >::iterator j=OUT[l].lower_bound(make_pair(tmp.first,0));
			if(j!=OUT[l].end()&&j->first==tmp.first){
				// printf("(%d)\n",tmp.first);
				mg.insert(tmp.first);
			}
		}
		for(set<pair<int,int> >::iterator i=OUT[r].begin();i!=OUT[r].end();i++){
			pair<int,int>tmp=*i;
			set<pair<int,int> >::iterator j=IN[l].lower_bound(make_pair(tmp.first,0));
			if(j!=IN[l].end()&&j->first==tmp.first){
				// printf("[%d]\n",tmp.first);
				mg.insert(tmp.first);
			}
		}
		for(set<pair<int,int> >::iterator i=IN[r].begin();i!=IN[r].end();i++){
			pair<int,int>tmp=*i;
			if(IN[l].count(tmp)==0){
				ret+=sl;
			}
			IN[l].insert(tmp);
		}

		// 餓뽧겗�꾠겇�뗣굢 r �ヤ섯�녈겍�꾠굥�귙겗��릫�띲굮l�ャ걢�덀굥
		for(set<pair<int,int> >::iterator i=OUT[r].begin();i!=OUT[r].end();i++){
			pair<int,int>tmp=*i;
			set<pair<int,int> >::iterator j=IN[tmp.first].lower_bound(make_pair(r,0));
			vector<pair<int,int> >tmp_del;
			while(j!=IN[tmp.first].end()&&j->first==r){
				tmp_del.push_back(*j);
				j++;
			}
			for(int j=0;j<tmp_del.size();j++){
				IN[tmp.first].erase(tmp_del[j]);
				IN[tmp.first].insert(make_pair(l,tmp_del[j].second));
			}

		}

		for(set<pair<int,int> >::iterator i=IN[r].begin();i!=IN[r].end();i++){
			pair<int,int>tmp=*i;
			set<pair<int,int> >::iterator j=OUT[tmp.first].lower_bound(make_pair(r,0));
			vector<pair<int,int> >tmp_del;
			while(j!=OUT[tmp.first].end()&&j->first==r){
				tmp_del.push_back(*j);
				j++;
			}
			for(int j=0;j<tmp_del.size();j++){
				OUT[tmp.first].erase(tmp_del[j]);
				OUT[tmp.first].insert(make_pair(l,tmp_del[j].second));
			}

		}
		

		// printf("%d %d %lld\n",l,r,ret);

		for(set<pair<int,int> >::iterator i=OUT[r].begin();i!=OUT[r].end();i++){
			OUT[l].insert(*i);
		}
		for(set<int>::iterator i=mg.begin();i!=mg.end();i++){
			Q.push(make_pair(l,*i));
		}
		UNION(l,r);
	}
}
int main(){
	int a,b;scanf("%d%d",&a,&b);
	for(int i=0;i<a;i++)par[i]=i;
	init_UF(a);
	for(int i=0;i<b;i++){
		int p,q;scanf("%d%d",&p,&q);p--;q--;
		int P=FIND(p);
		int Q=FIND(q);
		if(P==Q||OUT[P].count(make_pair(Q,p))){
			printf("%lld\n",ret);continue;
		}
		ae(P,Q,p,q);
		printf("%lld\n",ret);
	}
}

Compilation message (stderr)

joitter2.cpp: In function 'void ae(int, int, int, int)':
joitter2.cpp:131:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<del.size();i++)OUT[r].erase(del[i]);
               ~^~~~~~~~~~~
joitter2.cpp:140:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<del.size();i++)OUT[l].erase(del[i]);
               ~^~~~~~~~~~~
joitter2.cpp:147:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<del.size();i++)IN[l].erase(del[i]);
               ~^~~~~~~~~~~
joitter2.cpp:154:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<del.size();i++)IN[r].erase(del[i]);
               ~^~~~~~~~~~~
joitter2.cpp:229:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int j=0;j<tmp_del.size();j++){
                ~^~~~~~~~~~~~~~~
joitter2.cpp:244:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int j=0;j<tmp_del.size();j++){
                ~^~~~~~~~~~~~~~~
joitter2.cpp: In function 'int main()':
joitter2.cpp:264:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  int a,b;scanf("%d%d",&a,&b);
          ~~~~~^~~~~~~~~~~~~~
joitter2.cpp:268:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int p,q;scanf("%d%d",&p,&q);p--;q--;
           ~~~~~^~~~~~~~~~~~~~
joitter2.cpp: At global scope:
joitter2.cpp:84:6: warning: 'int {anonymous}::sig(double)' defined but not used [-Wunused-function]
  int sig(double r) { return (r < -EPS) ? -1 : (r > +EPS) ? +1 : 0; }
      ^~~
joitter2.cpp:83:9: warning: 'double {anonymous}::ABS(double)' defined but not used [-Wunused-function]
  double ABS(double a){return max(a,-a);}
         ^~~
joitter2.cpp:82:12: warning: 'long long int {anonymous}::ABS(long long int)' defined but not used [-Wunused-function]
  long long ABS(long long a){return max(a,-a);}
            ^~~
joitter2.cpp:81:6: warning: 'int {anonymous}::ABS(int)' defined but not used [-Wunused-function]
  int ABS(int a){return max(a,-a);}
      ^~~
joitter2.cpp:70:6: warning: 'int {anonymous}::pw_mod_int(int, int, int)' defined but not used [-Wunused-function]
  int pw_mod_int(int a,int b,int M){
      ^~~~~~~~~~
joitter2.cpp:59:12: warning: 'long long int {anonymous}::pw_mod(long long int, long long int, long long int)' defined but not used [-Wunused-function]
  long long pw_mod(long long a,long long b,long long M){
            ^~~~~~
joitter2.cpp:48:12: warning: 'long long int {anonymous}::pw(long long int, long long int)' defined but not used [-Wunused-function]
  long long pw(long long a,long long b){
            ^~
joitter2.cpp:38:7: warning: 'void {anonymous}::init_C(int)' defined but not used [-Wunused-function]
  void init_C(int n){
       ^~~~~~
joitter2.cpp:34:12: warning: 'long long int {anonymous}::Comb(int, int)' defined but not used [-Wunused-function]
  long long Comb(int a,int b){
            ^~~~

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