oj.uz

Submission #559600

# Submission time Handle Problem Language Result Execution time Memory
559600 2022-05-10T09:04:18 Z mosiashvililuka Simurgh (IOI17_simurgh) C++14
100 / 100
 202 ms 16364 KB 
#include<bits/stdc++.h>
#include "simurgh.h"
using namespace std;
int a,b,c,d,e,i,j,ii,jj,zx,xc,msh[200009],E,BO[200009],ans[200009],Q[200009],QI,W[200009],WI,p[200009],pi,dep[200009],O[503][503],st,bo[200009],lef,rig,mid,cnt;
pair <int, int> P[200009];
vector <int> v[200009],xe,vv[200009],VV,V;
int fnd(int q){
	if(msh[q]==0) return q; else return msh[q]=fnd(msh[q]);
}
bool mrg(int q, int w){
	q=fnd(q);w=fnd(w);
	if(q==w) return 0;
	msh[q]=w;
	return 1;
}
void dfs(int q, int w){
	msh[q]=w;dep[q]=dep[w]+1;
	for(vector <int>::iterator it=vv[q].begin(); it!=vv[q].end(); it++){
		if((*it)==w) continue;
		dfs((*it),q);
	}
}
vector <int> tofull(vector <int> q){
	vector <int> Q=q;
	cnt++;
	for(int h=0; h<q.size(); h++){
		int we=0;
		if(P[q[h]].first==ii) we=P[q[h]].second; else we=P[q[h]].first;
		int qw=O[we][msh[we]];bo[qw]=cnt;
	}
	for(int h=0; h<xe.size(); h++){
		if(bo[xe[h]]!=cnt){
			Q.push_back(xe[h]);
		}
	}
	return Q;
}
vector<int> find_roads(int Nn, std::vector<int> Uu, std::vector<int> Vv) {
	//int common = count_common_roads(r);
	a=Nn;b=Uu.size();
	for(i=0; i<Uu.size(); i++){
		P[i]={Uu[i]+1,Vv[i]+1};
		v[P[i].first].push_back(P[i].second);v[P[i].second].push_back(P[i].first);
		O[P[i].first][P[i].second]=O[P[i].second][P[i].first]=i;
	}
	for(i=0; i<b; i++){
		E=mrg(P[i].first,P[i].second);
		if(E==1){
			xe.push_back(i);BO[i]=1;
			vv[P[i].first].push_back(P[i].second);vv[P[i].second].push_back(P[i].first);
		}
	}
	st=count_common_roads(xe);
	for(i=0; i<b; i++) ans[i]=2;
	dfs(1,0);
	for(ii=0; ii<b; ii++){
		if(BO[ii]==0){
			QI=0;WI=0;pi=0;
			c=P[ii].first;d=P[ii].second;
			while(c!=d){
				if(dep[c]>=dep[d]){
					QI++;Q[QI]=c;c=msh[c];
				}else{
					WI++;W[WI]=d;d=msh[d];
				}
			}
			QI++;Q[QI]=c;
			for(i=1; i<=QI; i++){
				pi++;p[pi]=Q[i];
			}
			for(i=WI; i>=1; i--){
				pi++;p[pi]=W[i];
			}
			QI=0;
			for(i=1; i<pi; i++){
				c=O[p[i]][p[i+1]];
				if(ans[c]==2){
					QI++;Q[QI]=c;
				}
			}
			if(QI==0) continue;
			E=0;
			for(i=1; i<pi; i++){
				c=O[p[i]][p[i+1]];
				if(ans[c]!=2){
					QI++;Q[QI]=c;E=ans[c];break;
				}
			}
			if(QI==0){
				QI++;Q[QI]=O[p[1]][p[2]];
			}
			WI=0;
			for(i=1; i<=QI; i++){
				VV.clear();
				for(j=0; j<xe.size(); j++){
					if(xe[j]!=Q[i]){
						VV.push_back(xe[j]);
					}
				}
				VV.push_back(ii);
				WI++;W[WI]=count_common_roads(VV);
			}
			WI++;W[WI]=st;zx=0;xc=a+4;Q[WI]=ii;
			for(i=1; i<=WI; i++){
				zx=max(zx,W[i]);xc=min(xc,W[i]);
			}
			for(i=1; i<=WI; i++){
				if(zx==xc){
					ans[Q[i]]=E;
					//cout<<Q[i]<<" "<<E<<"\n";
					continue;
				}
				if(W[i]==zx){
					//cout<<Q[i]<<" 0\n";
					ans[Q[i]]=0;
				}else{
					//cout<<Q[i]<<" 1\n";
					ans[Q[i]]=1;
				}
			}
		}
	}
	for(ii=0; ii<b; ii++){
		if(BO[ii]==1){
			if(ans[ii]==2) ans[ii]=1;
		}
	}
	/*for(ii=0; ii<b; ii++){
		cout<<ans[ii]<<" ";
	}
	cout<<"\n";*/
	for(ii=1; ii<=a; ii++){
		dfs(ii,0);VV.clear();V.clear();
		for(vector <int>::iterator it=v[ii].begin(); it!=v[ii].end(); it++){
			c=O[ii][(*it)];
			if(ans[c]!=2) continue;
			VV.push_back(c);
		}
		if(VV.size()==0) continue;
		V=tofull(VV);
		zx=count_common_roads(V);
		for(int h=0; h<V.size(); h++){
			if(ans[V[h]]==1) zx--;
		}
		//cout<<ii-1<<" "<<zx<<"\n";
		E=-1;
		while(zx>0){
			lef=E;rig=VV.size();
			while(1){
				if(lef+1>=rig) break;
				mid=(lef+rig)/2;
				V.clear();
				for(int h=E+1; h<=mid; h++){
					V.push_back(VV[h]);
				}
				V=tofull(V);
				c=count_common_roads(V);
				//cout<<"c: "<<c<<"     "<<ii<<"      "<<lef<<" "<<mid<<" "<<rig<<"\n";
				for(int h=0; h<V.size(); h++){
					if(ans[V[h]]==1) c--;
				}
				//cout<<"c: "<<c<<"     "<<ii<<"      "<<lef<<" "<<mid<<" "<<rig<<"\n";
				if(c>0){
					rig=mid;
				}else{
					lef=mid;
				}
			}
			/*if(rig==VV.size()){
				cout<<"PANIC";exit(0);
			}*/
			for(int h=E+1; h<rig; h++) ans[VV[h]]=0;
			ans[VV[rig]]=1;
			zx--;E=rig;
		}
	}
	VV.clear();
	for(ii=0; ii<b; ii++){
		if(ans[ii]==1) VV.push_back(ii);
	}
	/*for(ii=0; ii<b; ii++){
		cout<<ans[ii]<<" ";
	}
	cout<<"\n";*/
	return VV;
}

Compilation message

simurgh.cpp: In function 'std::vector<int> tofull(std::vector<int>)':
simurgh.cpp:26:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |  for(int h=0; h<q.size(); h++){
      |               ~^~~~~~~~~
simurgh.cpp:31:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |  for(int h=0; h<xe.size(); h++){
      |               ~^~~~~~~~~~
simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:41:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |  for(i=0; i<Uu.size(); i++){
      |           ~^~~~~~~~~~
simurgh.cpp:95:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   95 |     for(j=0; j<xe.size(); j++){
      |              ~^~~~~~~~~~
simurgh.cpp:142:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  142 |   for(int h=0; h<V.size(); h++){
      |                ~^~~~~~~~~
simurgh.cpp:159:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  159 |     for(int h=0; h<V.size(); h++){
      |                  ~^~~~~~~~~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9684 KB correct
2 Correct 7 ms 9684 KB correct
3 Correct 6 ms 9684 KB correct
4 Correct 5 ms 9700 KB correct
5 Correct 5 ms 9684 KB correct
6 Correct 6 ms 9764 KB correct
7 Correct 5 ms 9684 KB correct
8 Correct 6 ms 9740 KB correct
9 Correct 5 ms 9700 KB correct
10 Correct 5 ms 9684 KB correct
11 Correct 7 ms 9700 KB correct
12 Correct 5 ms 9672 KB correct
13 Correct 5 ms 9684 KB correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9684 KB correct
2 Correct 7 ms 9684 KB correct
3 Correct 6 ms 9684 KB correct
4 Correct 5 ms 9700 KB correct
5 Correct 5 ms 9684 KB correct
6 Correct 6 ms 9764 KB correct
7 Correct 5 ms 9684 KB correct
8 Correct 6 ms 9740 KB correct
9 Correct 5 ms 9700 KB correct
10 Correct 5 ms 9684 KB correct
11 Correct 7 ms 9700 KB correct
12 Correct 5 ms 9672 KB correct
13 Correct 5 ms 9684 KB correct
14 Correct 7 ms 9860 KB correct
15 Correct 6 ms 9812 KB correct
16 Correct 6 ms 9836 KB correct
17 Correct 6 ms 9812 KB correct
18 Correct 6 ms 9828 KB correct
19 Correct 6 ms 9840 KB correct
20 Correct 8 ms 9840 KB correct
21 Correct 6 ms 9832 KB correct
22 Correct 7 ms 9812 KB correct
23 Correct 7 ms 9796 KB correct
24 Correct 6 ms 9880 KB correct
25 Correct 6 ms 9812 KB correct
26 Correct 5 ms 9812 KB correct
27 Correct 6 ms 9812 KB correct
28 Correct 5 ms 9812 KB correct
29 Correct 5 ms 9832 KB correct
30 Correct 6 ms 9812 KB correct
31 Correct 6 ms 9812 KB correct
32 Correct 6 ms 9812 KB correct
33 Correct 6 ms 9812 KB correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9684 KB correct
2 Correct 7 ms 9684 KB correct
3 Correct 6 ms 9684 KB correct
4 Correct 5 ms 9700 KB correct
5 Correct 5 ms 9684 KB correct
6 Correct 6 ms 9764 KB correct
7 Correct 5 ms 9684 KB correct
8 Correct 6 ms 9740 KB correct
9 Correct 5 ms 9700 KB correct
10 Correct 5 ms 9684 KB correct
11 Correct 7 ms 9700 KB correct
12 Correct 5 ms 9672 KB correct
13 Correct 5 ms 9684 KB correct
14 Correct 7 ms 9860 KB correct
15 Correct 6 ms 9812 KB correct
16 Correct 6 ms 9836 KB correct
17 Correct 6 ms 9812 KB correct
18 Correct 6 ms 9828 KB correct
19 Correct 6 ms 9840 KB correct
20 Correct 8 ms 9840 KB correct
21 Correct 6 ms 9832 KB correct
22 Correct 7 ms 9812 KB correct
23 Correct 7 ms 9796 KB correct
24 Correct 6 ms 9880 KB correct
25 Correct 6 ms 9812 KB correct
26 Correct 5 ms 9812 KB correct
27 Correct 6 ms 9812 KB correct
28 Correct 5 ms 9812 KB correct
29 Correct 5 ms 9832 KB correct
30 Correct 6 ms 9812 KB correct
31 Correct 6 ms 9812 KB correct
32 Correct 6 ms 9812 KB correct
33 Correct 6 ms 9812 KB correct
34 Correct 40 ms 11496 KB correct
35 Correct 43 ms 11476 KB correct
36 Correct 40 ms 11164 KB correct
37 Correct 14 ms 10224 KB correct
38 Correct 38 ms 11460 KB correct
39 Correct 35 ms 11348 KB correct
40 Correct 32 ms 11092 KB correct
41 Correct 40 ms 11504 KB correct
42 Correct 40 ms 11380 KB correct
43 Correct 15 ms 10980 KB correct
44 Correct 13 ms 10708 KB correct
45 Correct 15 ms 10784 KB correct
46 Correct 13 ms 10736 KB correct
47 Correct 12 ms 10476 KB correct
48 Correct 9 ms 10232 KB correct
49 Correct 12 ms 10308 KB correct
50 Correct 13 ms 10484 KB correct
51 Correct 17 ms 10836 KB correct
52 Correct 14 ms 10760 KB correct
53 Correct 14 ms 10708 KB correct
54 Correct 15 ms 10928 KB correct
55 Correct 16 ms 10860 KB correct
56 Correct 16 ms 10836 KB correct
57 Correct 16 ms 10836 KB correct

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9684 KB correct
2 Correct 6 ms 9704 KB correct
3 Correct 119 ms 14276 KB correct
4 Correct 174 ms 16288 KB correct
5 Correct 172 ms 16236 KB correct
6 Correct 170 ms 16264 KB correct
7 Correct 175 ms 16224 KB correct
8 Correct 150 ms 16276 KB correct
9 Correct 171 ms 16284 KB correct
10 Correct 202 ms 16296 KB correct
11 Correct 173 ms 16304 KB correct
12 Correct 188 ms 16272 KB correct
13 Correct 6 ms 9684 KB correct
14 Correct 186 ms 16252 KB correct
15 Correct 174 ms 16364 KB correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9684 KB correct
2 Correct 7 ms 9684 KB correct
3 Correct 6 ms 9684 KB correct
4 Correct 5 ms 9700 KB correct
5 Correct 5 ms 9684 KB correct
6 Correct 6 ms 9764 KB correct
7 Correct 5 ms 9684 KB correct
8 Correct 6 ms 9740 KB correct
9 Correct 5 ms 9700 KB correct
10 Correct 5 ms 9684 KB correct
11 Correct 7 ms 9700 KB correct
12 Correct 5 ms 9672 KB correct
13 Correct 5 ms 9684 KB correct
14 Correct 7 ms 9860 KB correct
15 Correct 6 ms 9812 KB correct
16 Correct 6 ms 9836 KB correct
17 Correct 6 ms 9812 KB correct
18 Correct 6 ms 9828 KB correct
19 Correct 6 ms 9840 KB correct
20 Correct 8 ms 9840 KB correct
21 Correct 6 ms 9832 KB correct
22 Correct 7 ms 9812 KB correct
23 Correct 7 ms 9796 KB correct
24 Correct 6 ms 9880 KB correct
25 Correct 6 ms 9812 KB correct
26 Correct 5 ms 9812 KB correct
27 Correct 6 ms 9812 KB correct
28 Correct 5 ms 9812 KB correct
29 Correct 5 ms 9832 KB correct
30 Correct 6 ms 9812 KB correct
31 Correct 6 ms 9812 KB correct
32 Correct 6 ms 9812 KB correct
33 Correct 6 ms 9812 KB correct
34 Correct 40 ms 11496 KB correct
35 Correct 43 ms 11476 KB correct
36 Correct 40 ms 11164 KB correct
37 Correct 14 ms 10224 KB correct
38 Correct 38 ms 11460 KB correct
39 Correct 35 ms 11348 KB correct
40 Correct 32 ms 11092 KB correct
41 Correct 40 ms 11504 KB correct
42 Correct 40 ms 11380 KB correct
43 Correct 15 ms 10980 KB correct
44 Correct 13 ms 10708 KB correct
45 Correct 15 ms 10784 KB correct
46 Correct 13 ms 10736 KB correct
47 Correct 12 ms 10476 KB correct
48 Correct 9 ms 10232 KB correct
49 Correct 12 ms 10308 KB correct
50 Correct 13 ms 10484 KB correct
51 Correct 17 ms 10836 KB correct
52 Correct 14 ms 10760 KB correct
53 Correct 14 ms 10708 KB correct
54 Correct 15 ms 10928 KB correct
55 Correct 16 ms 10860 KB correct
56 Correct 16 ms 10836 KB correct
57 Correct 16 ms 10836 KB correct
58 Correct 6 ms 9684 KB correct
59 Correct 6 ms 9704 KB correct
60 Correct 119 ms 14276 KB correct
61 Correct 174 ms 16288 KB correct
62 Correct 172 ms 16236 KB correct
63 Correct 170 ms 16264 KB correct
64 Correct 175 ms 16224 KB correct
65 Correct 150 ms 16276 KB correct
66 Correct 171 ms 16284 KB correct
67 Correct 202 ms 16296 KB correct
68 Correct 173 ms 16304 KB correct
69 Correct 188 ms 16272 KB correct
70 Correct 6 ms 9684 KB correct
71 Correct 186 ms 16252 KB correct
72 Correct 174 ms 16364 KB correct
73 Correct 6 ms 9684 KB correct
74 Correct 195 ms 16292 KB correct
75 Correct 193 ms 16144 KB correct
76 Correct 85 ms 12620 KB correct
77 Correct 191 ms 16280 KB correct
78 Correct 180 ms 16324 KB correct
79 Correct 185 ms 16284 KB correct
80 Correct 184 ms 16016 KB correct
81 Correct 142 ms 15436 KB correct
82 Correct 181 ms 16116 KB correct
83 Correct 134 ms 13672 KB correct
84 Correct 55 ms 14128 KB correct
85 Correct 52 ms 14040 KB correct
86 Correct 44 ms 12876 KB correct
87 Correct 38 ms 12388 KB correct
88 Correct 34 ms 11848 KB correct
89 Correct 33 ms 11880 KB correct
90 Correct 34 ms 11752 KB correct
91 Correct 21 ms 10864 KB correct
92 Correct 17 ms 10816 KB correct
93 Correct 52 ms 13916 KB correct
94 Correct 42 ms 12892 KB correct
95 Correct 41 ms 12756 KB correct
96 Correct 32 ms 11896 KB correct
97 Correct 34 ms 11948 KB correct
98 Correct 38 ms 12376 KB correct
99 Correct 37 ms 11860 KB correct
100 Correct 26 ms 11092 KB correct
101 Correct 18 ms 10812 KB correct
102 Correct 56 ms 13544 KB correct
103 Correct 54 ms 13516 KB correct
104 Correct 57 ms 13460 KB correct
105 Correct 53 ms 13492 KB correct