oj.uz

Submission #216314

# Submission time Handle Problem Language Result Execution time Memory
216314 2020-03-27T05:12:06 Z model_code Making Friends on Joitter is Fun (JOI20_joitter2) C++17
100 / 100
 1198 ms 54520 KB 
#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

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.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 19968 KB Output is correct
2 Correct 16 ms 20096 KB Output is correct
3 Correct 16 ms 20096 KB Output is correct
4 Correct 16 ms 20096 KB Output is correct
5 Correct 16 ms 20096 KB Output is correct
6 Correct 17 ms 20096 KB Output is correct
7 Correct 17 ms 20096 KB Output is correct
8 Correct 18 ms 20096 KB Output is correct
9 Correct 20 ms 20096 KB Output is correct
10 Correct 18 ms 20096 KB Output is correct
11 Correct 16 ms 20096 KB Output is correct
12 Correct 16 ms 20096 KB Output is correct
13 Correct 16 ms 20096 KB Output is correct
14 Correct 17 ms 20096 KB Output is correct
15 Correct 17 ms 20096 KB Output is correct
16 Correct 19 ms 20096 KB Output is correct
17 Correct 17 ms 20096 KB Output is correct
18 Correct 19 ms 20096 KB Output is correct
19 Correct 17 ms 20096 KB Output is correct
20 Correct 16 ms 20096 KB Output is correct
21 Correct 17 ms 20096 KB Output is correct
22 Correct 16 ms 20096 KB Output is correct
23 Correct 20 ms 20096 KB Output is correct
24 Correct 20 ms 20096 KB Output is correct
25 Correct 17 ms 20096 KB Output is correct
26 Correct 17 ms 20096 KB Output is correct
27 Correct 15 ms 20096 KB Output is correct
28 Correct 19 ms 20096 KB Output is correct
29 Correct 17 ms 20096 KB Output is correct
30 Correct 17 ms 20096 KB Output is correct
31 Correct 19 ms 20096 KB Output is correct
32 Correct 17 ms 20096 KB Output is correct
33 Correct 19 ms 20096 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 19968 KB Output is correct
2 Correct 16 ms 20096 KB Output is correct
3 Correct 16 ms 20096 KB Output is correct
4 Correct 16 ms 20096 KB Output is correct
5 Correct 16 ms 20096 KB Output is correct
6 Correct 17 ms 20096 KB Output is correct
7 Correct 17 ms 20096 KB Output is correct
8 Correct 18 ms 20096 KB Output is correct
9 Correct 20 ms 20096 KB Output is correct
10 Correct 18 ms 20096 KB Output is correct
11 Correct 16 ms 20096 KB Output is correct
12 Correct 16 ms 20096 KB Output is correct
13 Correct 16 ms 20096 KB Output is correct
14 Correct 17 ms 20096 KB Output is correct
15 Correct 17 ms 20096 KB Output is correct
16 Correct 19 ms 20096 KB Output is correct
17 Correct 17 ms 20096 KB Output is correct
18 Correct 19 ms 20096 KB Output is correct
19 Correct 17 ms 20096 KB Output is correct
20 Correct 16 ms 20096 KB Output is correct
21 Correct 17 ms 20096 KB Output is correct
22 Correct 16 ms 20096 KB Output is correct
23 Correct 20 ms 20096 KB Output is correct
24 Correct 20 ms 20096 KB Output is correct
25 Correct 17 ms 20096 KB Output is correct
26 Correct 17 ms 20096 KB Output is correct
27 Correct 15 ms 20096 KB Output is correct
28 Correct 19 ms 20096 KB Output is correct
29 Correct 17 ms 20096 KB Output is correct
30 Correct 17 ms 20096 KB Output is correct
31 Correct 19 ms 20096 KB Output is correct
32 Correct 17 ms 20096 KB Output is correct
33 Correct 19 ms 20096 KB Output is correct
34 Correct 19 ms 20224 KB Output is correct
35 Correct 146 ms 25336 KB Output is correct
36 Correct 186 ms 27688 KB Output is correct
37 Correct 186 ms 27424 KB Output is correct
38 Correct 186 ms 27388 KB Output is correct
39 Correct 18 ms 20224 KB Output is correct
40 Correct 20 ms 20240 KB Output is correct
41 Correct 20 ms 20224 KB Output is correct
42 Correct 30 ms 20224 KB Output is correct
43 Correct 20 ms 20224 KB Output is correct
44 Correct 23 ms 20224 KB Output is correct
45 Correct 18 ms 20100 KB Output is correct
46 Correct 18 ms 20224 KB Output is correct
47 Correct 25 ms 20224 KB Output is correct
48 Correct 22 ms 20224 KB Output is correct
49 Correct 29 ms 20864 KB Output is correct
50 Correct 183 ms 27524 KB Output is correct
51 Correct 30 ms 20480 KB Output is correct
52 Correct 147 ms 26460 KB Output is correct
53 Correct 30 ms 20864 KB Output is correct
54 Correct 159 ms 26980 KB Output is correct
55 Correct 23 ms 20608 KB Output is correct
56 Correct 23 ms 20480 KB Output is correct
57 Correct 26 ms 20480 KB Output is correct
58 Correct 22 ms 20480 KB Output is correct
59 Correct 18 ms 20096 KB Output is correct
60 Correct 128 ms 25056 KB Output is correct
61 Correct 26 ms 20352 KB Output is correct
62 Correct 216 ms 27196 KB Output is correct

Subtask #3
83.0 / 83.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 19968 KB Output is correct
2 Correct 16 ms 20096 KB Output is correct
3 Correct 16 ms 20096 KB Output is correct
4 Correct 16 ms 20096 KB Output is correct
5 Correct 16 ms 20096 KB Output is correct
6 Correct 17 ms 20096 KB Output is correct
7 Correct 17 ms 20096 KB Output is correct
8 Correct 18 ms 20096 KB Output is correct
9 Correct 20 ms 20096 KB Output is correct
10 Correct 18 ms 20096 KB Output is correct
11 Correct 16 ms 20096 KB Output is correct
12 Correct 16 ms 20096 KB Output is correct
13 Correct 16 ms 20096 KB Output is correct
14 Correct 17 ms 20096 KB Output is correct
15 Correct 17 ms 20096 KB Output is correct
16 Correct 19 ms 20096 KB Output is correct
17 Correct 17 ms 20096 KB Output is correct
18 Correct 19 ms 20096 KB Output is correct
19 Correct 17 ms 20096 KB Output is correct
20 Correct 16 ms 20096 KB Output is correct
21 Correct 17 ms 20096 KB Output is correct
22 Correct 16 ms 20096 KB Output is correct
23 Correct 20 ms 20096 KB Output is correct
24 Correct 20 ms 20096 KB Output is correct
25 Correct 17 ms 20096 KB Output is correct
26 Correct 17 ms 20096 KB Output is correct
27 Correct 15 ms 20096 KB Output is correct
28 Correct 19 ms 20096 KB Output is correct
29 Correct 17 ms 20096 KB Output is correct
30 Correct 17 ms 20096 KB Output is correct
31 Correct 19 ms 20096 KB Output is correct
32 Correct 17 ms 20096 KB Output is correct
33 Correct 19 ms 20096 KB Output is correct
34 Correct 19 ms 20224 KB Output is correct
35 Correct 146 ms 25336 KB Output is correct
36 Correct 186 ms 27688 KB Output is correct
37 Correct 186 ms 27424 KB Output is correct
38 Correct 186 ms 27388 KB Output is correct
39 Correct 18 ms 20224 KB Output is correct
40 Correct 20 ms 20240 KB Output is correct
41 Correct 20 ms 20224 KB Output is correct
42 Correct 30 ms 20224 KB Output is correct
43 Correct 20 ms 20224 KB Output is correct
44 Correct 23 ms 20224 KB Output is correct
45 Correct 18 ms 20100 KB Output is correct
46 Correct 18 ms 20224 KB Output is correct
47 Correct 25 ms 20224 KB Output is correct
48 Correct 22 ms 20224 KB Output is correct
49 Correct 29 ms 20864 KB Output is correct
50 Correct 183 ms 27524 KB Output is correct
51 Correct 30 ms 20480 KB Output is correct
52 Correct 147 ms 26460 KB Output is correct
53 Correct 30 ms 20864 KB Output is correct
54 Correct 159 ms 26980 KB Output is correct
55 Correct 23 ms 20608 KB Output is correct
56 Correct 23 ms 20480 KB Output is correct
57 Correct 26 ms 20480 KB Output is correct
58 Correct 22 ms 20480 KB Output is correct
59 Correct 18 ms 20096 KB Output is correct
60 Correct 128 ms 25056 KB Output is correct
61 Correct 26 ms 20352 KB Output is correct
62 Correct 216 ms 27196 KB Output is correct
63 Correct 596 ms 54520 KB Output is correct
64 Correct 612 ms 54520 KB Output is correct
65 Correct 610 ms 54508 KB Output is correct
66 Correct 212 ms 25280 KB Output is correct
67 Correct 366 ms 29560 KB Output is correct
68 Correct 202 ms 25292 KB Output is correct
69 Correct 456 ms 29872 KB Output is correct
70 Correct 210 ms 25244 KB Output is correct
71 Correct 214 ms 25260 KB Output is correct
72 Correct 402 ms 29816 KB Output is correct
73 Correct 384 ms 29916 KB Output is correct
74 Correct 1198 ms 48152 KB Output is correct
75 Correct 763 ms 35320 KB Output is correct
76 Correct 823 ms 41472 KB Output is correct
77 Correct 778 ms 41524 KB Output is correct
78 Correct 267 ms 29920 KB Output is correct
79 Correct 474 ms 33700 KB Output is correct
80 Correct 297 ms 30044 KB Output is correct
81 Correct 398 ms 33272 KB Output is correct
82 Correct 840 ms 44260 KB Output is correct
83 Correct 854 ms 44076 KB Output is correct
84 Correct 638 ms 43564 KB Output is correct
85 Correct 630 ms 43404 KB Output is correct
86 Correct 212 ms 24440 KB Output is correct
87 Correct 264 ms 26744 KB Output is correct
88 Correct 383 ms 29944 KB Output is correct
89 Correct 749 ms 40280 KB Output is correct