oj.uz

Submission #400053

# Submission time Handle Problem Language Result Execution time Memory
400053 2021-05-07T09:19:06 Z kshitij_sodani Simurgh (IOI17_simurgh) C++14
51 / 100
 3000 ms 5672 KB 
//#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
typedef long long llo;
#define mp make_pair
#define pb push_back
#define a first 
#define b second
#define endl '\n'
#define ask ask3
//#define ask3 
#include "simurgh.h"
int par[513];
int par2[513];
int count3=0;
int tt[500*500];
int ask3(vector<int> xx){

	count3++;
	return count_common_roads(xx);
}
vector<pair<int,int>> adj[513];
int ind5[513][513];
int n;
int vis[513];
vector<int> uu;
vector<int> vv;
int find(int no){
	if(par[no]==no){
		return no;
	}
	par[no]=find(par[no]);
	return par[no];
}
int find2(int no){
	if(par2[no]==no){
		return no;
	}
	par2[no]=find2(par2[no]);
	return par2[no];
}
int ca=-1;
vector<int> pp;
vector<int> pp2;
void dfs(int no,int par2=-1){
	if(no==ca){
		pp2=pp;
	}
	for(auto j:adj[no]){
		if(j.a!=par2){
			pp.pb(j.b);
			dfs(j.a,no);
			pp.pop_back();
		}
	}
}
vector<int> ans2;
vector<int> ans;
int count2=0;
int ask2(vector<pair<int,int>> cur){
	for(int i=0;i<n;i++){
		adj[i].clear();
	}
	for(int i=0;i<uu.size();i++){
		if(tt[i]==0){
			adj[uu[i]].pb({vv[i],i});
			adj[vv[i]].pb({uu[i],i});
		}
	}
	for(auto j:cur){
		ca=j.b;
		dfs(j.a);
		for(auto i:pp2){
			if(tt[i]==0){
				for(int ii=0;ii<n;ii++){
					vector<pair<int,int>> ne;
					for(auto jj:adj[ii]){
						if(jj.b!=i){
							ne.pb(jj);
						}
					}
					adj[ii]=ne;
				}
				adj[j.a].pb({j.b,ind5[j.a][j.b]});
				adj[j.b].pb({j.a,ind5[j.a][j.b]});
				break;
			}
		}
	}
	vector<int> qq;
	for(int i=0;i<n;i++){
		for(auto j:adj[i]){
			if(j.a>i){
				qq.pb(j.b);
			}
		}
	}




	/*cout<<11<<endl;
	for(auto i:cur){
		cout<<i.a<<"::"<<i.b<<endl;
	}*/
	/*for(int i=0;i<n;i++){
		vis[i]=0;
	}
	for(auto i:cur){
		vis[i.a]=1;
		vis[i.b]=1;
	}*/
/*	for(auto i:cur){
		cout<<i.a<<"::"<<i.b<<endl;
	}*/
	
	int xx=0;
	/*for(int i=1;i<n;i++){
		if(vis[i]==0){
			qq.pb(ind5[0][i]);

		}
	}
	for(auto i:cur){
		qq.pb(ind5[i.a][i.b]);
		qq.pb(ind5[0][i.a]);
	}*/
	for(auto j:qq){
		if(tt[j]==0){
			if(ans[j]==1){
				xx--;

			}
		}
	}
	/*for(auto j:qq){
		cout<<j<<".";
	}
	cout<<endl;*/
	xx+=ask(qq);
	count2++;
	//cout<<xx<<endl;
	//cout<<endl;
	
	//cout<<xx<<endl<<endl;

	return xx;

}
void solve(vector<pair<int,int>> xx,int val2){
	if(val2==0){
		return;
	}
	if(xx.size()==1){
		//f(xx[0].b>xx[0].a+1 and xx[0].a!=0){
			ans[ind5[xx[0].a][xx[0].b]]=1;
			ans2.pb(ind5[xx[0].a][xx[0].b]);
		//}
	}
	else{
		vector<pair<int,int>> yy;
		vector<pair<int,int>> zz;
		for(int i=0;i<xx.size()/2;i++){
			yy.pb(xx[i]);
		}
		for(int i=xx.size()/2;i<xx.size();i++){
			zz.pb(xx[i]);
		}
		int val3=ask2(yy);
		solve(yy,val3);
		solve(zz,val2-val3);
	}
}

vector<int> find_roads(int nnn,vector<int> uuu,vector<int> vvv) {
	uu=uuu;
	vv=vvv;
	int m=uu.size();

	n=nnn;
	/*if(nnn<=240){
		return  find_roads2(n,uu,vv);
	}*/
	count3=0;
	count2=0;
	for(int i=0;i<n;i++){
		par[i]=i;
		par2[i]=i;
	}
	vector<pair<pair<int,int>,int>> cur;
	vector<pair<pair<int,int>,int>> cur2;
	vector<pair<pair<int,int>,int>> cur3;
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			ind5[i][j]=-1;
		}
	}
	for(int i=0;i<m;i++){
		ans.pb(0);
	}
	for(int i=0;i<m;i++){
		if(uu[i]>vv[i]){
			swap(uu[i],vv[i]);
		}
		ind5[uu[i]][vv[i]]=i;
		int x=find(uu[i]);
		int y=find(vv[i]);
		/*if(uu[i]!=0){
			if(abs(uu[i]-vv[i])>1){
				continue;
			}
		}*/
		if(x!=y){
			par[x]=y;
			tt[i]=0;
			cur.pb({{uu[i],vv[i]},i});
			adj[uu[i]].pb({vv[i],i});
			adj[vv[i]].pb({uu[i],i});
		}
		else{
			x=find2(uu[i]);
			y=find2(vv[i]);
			if(x!=y){
				tt[i]=1;
				par2[x]=y;
				cur2.pb({{uu[i],vv[i]},i});
			}
			else{
				tt[i]=2;
				cur3.pb({{uu[i],vv[i]},i});
				ans[i]=-2;
			}
		}
	}
	//mt19937 rng;
	//rng=mt19937(chrono::steady_clock::now().time_since_epoch().count());
	int val;
	vector<int> ee;
	for(auto j:cur){
		ee.pb(j.b);
	}
	val=ask(ee);
	count2++;
	
	/*for(int i=0;i<m;i++){
		if(uu[i]!=0){
			if(abs(uu[i]-vv[i])>1){
				ans.pb(-2);
				continue;
			}
		}
		ans.pb(0);
	}*/

	for(auto j:cur2){

		ca=j.a.b;
		dfs(j.a.a);
		int cur=-1;
		for(auto i:pp2){
			if(ans[i]!=0){
				cur=i;
			}
		}
	/*	for(auto i:pp2){
			cout<<i<<",";
		}
		cout<<endl;*/
		if(cur==-1){
			vector<pair<int,int>> xx;
			xx.pb({val,j.b});
			for(auto i:pp2){
				vector<int> ff;
				for(auto jj:ee){
					if(jj!=i){
						ff.pb(jj);
					}
				}
				ff.pb(j.b);
				int val2=ask(ff);
				count2++;
				xx.pb({val2,i});
			}
			sort(xx.begin(),xx.end());
			for(int i=0;i<xx.size();i++){
				if(xx[i].a==xx.back().a-1){
					ans[xx[i].b]=1;
				}
				else{
					ans[xx[i].b]=-1;
				}
			}
			/*for(auto j:xx){
				cout<<j.a<<"::"<<j.b<<endl;
			}
			cout<<endl;*/
		}
		else{
			if(true){
				vector<int> ff;
				for(auto jj:ee){
					if(jj!=cur){
						ff.pb(jj);
					}
				}
				ff.pb(j.b);
				int val2=ask(ff);
				count2++;
				int xx=val;
				if(ans[cur]==1){
					xx--;
				}
				if(val2==xx){
					ans[j.b]=-1;
				}
				else{
					ans[j.b]=1;
				}
			}
			for(auto i:pp2){
				if(ans[i]!=0){
					continue;
				}
				vector<int> ff;
				for(auto jj:ee){
					if(jj!=i){
						ff.pb(jj);
					}
				}
				ff.pb(j.b);
				int val2=ask(ff);
				count2++;
				int xx=val;
				if(ans[j.b]==1){
					xx+=1;
				}
				if(val2==xx){
					ans[i]=-1;
				}
				else{	
					ans[i]=1;
				}
			}
		}
	/*	for(auto i:ans){
			cout<<i<<".";
		}
		cout<<endl;*/

	}
	vector<vector<pair<int,int>>> qq;
	for(int i=1;i<=256;i*=2){
		vector<vector<int>> aa;
		vector<vector<int>> bb;
		for(int j=0;j<512;j+=i){
			vector<int> cc;
			for(int k=j;k<j+i;k++){
				cc.pb(k);
			}
			if((j/i)%2==0){
				aa.pb(cc);
			}
			else{
				bb.pb(cc);
			}
		}
		for(int j=0;j<i;j++){
			for(int k=0;k<bb.size();k++){
				vector<int> dd;
				for(int ii=1;ii<i;ii++){
					dd.pb(bb[k][ii]);
				}
				dd.pb(bb[k][0]);
				bb[k]=dd;
			}
			vector<pair<int,int>> rr;
			for(int k=0;k<aa.size();k++){
				for(int l=0;l<aa[k].size();l++){
					rr.pb({aa[k][l],bb[k][l]});
				}
			}
			qq.pb(rr);
		}
	}

	
	
	for(int i=0;i<m;i++){
		if(ans[i]==0){
			ans[i]=1;
		}
		if(ans[i]==1){
			ans2.pb(i);
		}
		//cout<<ans[i]<<":";
	}
	//cout<<endl;
	//cout<<cur3.size()<<endl;
	for(auto j:qq){
		vector<pair<int,int>> cur;

		for(auto i:j){
			if(i.a<n and i.b<n){
				/*if(i.a==2 and i.b==3){
					cout<<11<<endl;
				}*/
				if(ind5[i.a][i.b]!=-1){
					if(ans[ind5[i.a][i.b]]==-2){
						cur.pb(i);
					}
				}
			}
		}
		if(cur.size()){
		/*	for(auto i:cur){
				cout<<i.a<<"::"<<i.b<<endl;
			}
			cout<<endl;*/
			solve(cur,ask2(cur));
		}
	}
/*	 for(int i=0;i<m;i++){
		cout<<ans[i]<<":";
	 }
	 cout<<endl;
*/
	assert(count3<=8000);
	//cout<<count3<<endl;
	return ans2;



/*	shuffle(cur2.begin(),cur2.end(),rng);
	for(auto j:cur2){
		if(val==n-1){
			break;
		}
		for(int i=0;i<n;i++){
			adj[i].clear();
		}
		for(auto i:cur){
			adj[i.a.a].pb({i.a.b,i.b});
			adj[i.a.b].pb({i.a.a,i.b});
		}
		ca=j.a.b;
		dfs(j.a.a);
		shuffle(pp2.begin(),pp2.end(),rng);
		for(auto i:pp2){
			vector<int> ff;
			for(auto jj:ee){
				if(jj!=i){
					ff.pb(jj);
				}
			}
			ff.pb(j.b);
			int val2=ask(ff);
			if(val2<val){
				break;
			}
			if(val2==val){
				continue;
			}
			vector<pair<pair<int,int>,int>> cur3;
			for(auto ii:cur){
				if(ii.b==i){
					continue;
				}
				cur3.pb(ii);
			}
			cur3.pb(j);
			cur=cur3;
			val=val2;
			ee=ff;
			break;
		}
	}*/
//	return ee;
}

Compilation message

simurgh.cpp: In function 'int ask2(std::vector<std::pair<int, int> >)':
simurgh.cpp:65:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |  for(int i=0;i<uu.size();i++){
      |              ~^~~~~~~~~~
simurgh.cpp: In function 'void solve(std::vector<std::pair<int, int> >, int)':
simurgh.cpp:164:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  164 |   for(int i=0;i<xx.size()/2;i++){
      |               ~^~~~~~~~~~~~
simurgh.cpp:167:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  167 |   for(int i=xx.size()/2;i<xx.size();i++){
      |                         ~^~~~~~~~~~
simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:286:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  286 |    for(int i=0;i<xx.size();i++){
      |                ~^~~~~~~~~~
simurgh.cpp:369:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  369 |    for(int k=0;k<bb.size();k++){
      |                ~^~~~~~~~~~
simurgh.cpp:378:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  378 |    for(int k=0;k<aa.size();k++){
      |                ~^~~~~~~~~~
simurgh.cpp:379:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  379 |     for(int l=0;l<aa[k].size();l++){
      |                 ~^~~~~~~~~~~~~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1360 KB correct
2 Correct 4 ms 1356 KB correct
3 Correct 4 ms 1356 KB correct
4 Correct 4 ms 1356 KB correct
5 Correct 4 ms 1356 KB correct
6 Correct 4 ms 1356 KB correct
7 Correct 4 ms 1356 KB correct
8 Correct 4 ms 1356 KB correct
9 Correct 4 ms 1360 KB correct
10 Correct 4 ms 1356 KB correct
11 Correct 4 ms 1320 KB correct
12 Correct 4 ms 1356 KB correct
13 Correct 4 ms 1356 KB correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1360 KB correct
2 Correct 4 ms 1356 KB correct
3 Correct 4 ms 1356 KB correct
4 Correct 4 ms 1356 KB correct
5 Correct 4 ms 1356 KB correct
6 Correct 4 ms 1356 KB correct
7 Correct 4 ms 1356 KB correct
8 Correct 4 ms 1356 KB correct
9 Correct 4 ms 1360 KB correct
10 Correct 4 ms 1356 KB correct
11 Correct 4 ms 1320 KB correct
12 Correct 4 ms 1356 KB correct
13 Correct 4 ms 1356 KB correct
14 Correct 13 ms 1548 KB correct
15 Correct 14 ms 1556 KB correct
16 Correct 14 ms 1484 KB correct
17 Correct 12 ms 1532 KB correct
18 Correct 7 ms 1484 KB correct
19 Correct 12 ms 1540 KB correct
20 Correct 11 ms 1424 KB correct
21 Correct 11 ms 1432 KB correct
22 Correct 8 ms 1536 KB correct
23 Correct 7 ms 1484 KB correct
24 Correct 7 ms 1532 KB correct
25 Correct 4 ms 1484 KB correct
26 Correct 7 ms 1484 KB correct
27 Correct 8 ms 1484 KB correct
28 Correct 5 ms 1484 KB correct
29 Correct 5 ms 1484 KB correct
30 Correct 9 ms 1484 KB correct
31 Correct 7 ms 1524 KB correct
32 Correct 7 ms 1484 KB correct
33 Correct 7 ms 1408 KB correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1360 KB correct
2 Correct 4 ms 1356 KB correct
3 Correct 4 ms 1356 KB correct
4 Correct 4 ms 1356 KB correct
5 Correct 4 ms 1356 KB correct
6 Correct 4 ms 1356 KB correct
7 Correct 4 ms 1356 KB correct
8 Correct 4 ms 1356 KB correct
9 Correct 4 ms 1360 KB correct
10 Correct 4 ms 1356 KB correct
11 Correct 4 ms 1320 KB correct
12 Correct 4 ms 1356 KB correct
13 Correct 4 ms 1356 KB correct
14 Correct 13 ms 1548 KB correct
15 Correct 14 ms 1556 KB correct
16 Correct 14 ms 1484 KB correct
17 Correct 12 ms 1532 KB correct
18 Correct 7 ms 1484 KB correct
19 Correct 12 ms 1540 KB correct
20 Correct 11 ms 1424 KB correct
21 Correct 11 ms 1432 KB correct
22 Correct 8 ms 1536 KB correct
23 Correct 7 ms 1484 KB correct
24 Correct 7 ms 1532 KB correct
25 Correct 4 ms 1484 KB correct
26 Correct 7 ms 1484 KB correct
27 Correct 8 ms 1484 KB correct
28 Correct 5 ms 1484 KB correct
29 Correct 5 ms 1484 KB correct
30 Correct 9 ms 1484 KB correct
31 Correct 7 ms 1524 KB correct
32 Correct 7 ms 1484 KB correct
33 Correct 7 ms 1408 KB correct
34 Correct 1062 ms 3132 KB correct
35 Correct 1016 ms 3088 KB correct
36 Correct 708 ms 2636 KB correct
37 Correct 36 ms 1908 KB correct
38 Correct 1045 ms 3100 KB correct
39 Correct 924 ms 2940 KB correct
40 Correct 699 ms 2756 KB correct
41 Correct 1186 ms 3020 KB correct
42 Correct 1185 ms 3136 KB correct
43 Correct 316 ms 2468 KB correct
44 Correct 252 ms 2340 KB correct
45 Correct 299 ms 2496 KB correct
46 Correct 221 ms 2336 KB correct
47 Correct 100 ms 2068 KB correct
48 Correct 8 ms 1868 KB correct
49 Correct 30 ms 1916 KB correct
50 Correct 101 ms 2092 KB correct
51 Correct 300 ms 2468 KB correct
52 Correct 256 ms 2340 KB correct
53 Correct 227 ms 2340 KB correct
54 Correct 325 ms 2560 KB correct
55 Correct 309 ms 2468 KB correct
56 Correct 298 ms 2504 KB correct
57 Correct 303 ms 2512 KB correct

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1356 KB correct
2 Correct 4 ms 1356 KB correct
3 Execution timed out 3050 ms 5672 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1360 KB correct
2 Correct 4 ms 1356 KB correct
3 Correct 4 ms 1356 KB correct
4 Correct 4 ms 1356 KB correct
5 Correct 4 ms 1356 KB correct
6 Correct 4 ms 1356 KB correct
7 Correct 4 ms 1356 KB correct
8 Correct 4 ms 1356 KB correct
9 Correct 4 ms 1360 KB correct
10 Correct 4 ms 1356 KB correct
11 Correct 4 ms 1320 KB correct
12 Correct 4 ms 1356 KB correct
13 Correct 4 ms 1356 KB correct
14 Correct 13 ms 1548 KB correct
15 Correct 14 ms 1556 KB correct
16 Correct 14 ms 1484 KB correct
17 Correct 12 ms 1532 KB correct
18 Correct 7 ms 1484 KB correct
19 Correct 12 ms 1540 KB correct
20 Correct 11 ms 1424 KB correct
21 Correct 11 ms 1432 KB correct
22 Correct 8 ms 1536 KB correct
23 Correct 7 ms 1484 KB correct
24 Correct 7 ms 1532 KB correct
25 Correct 4 ms 1484 KB correct
26 Correct 7 ms 1484 KB correct
27 Correct 8 ms 1484 KB correct
28 Correct 5 ms 1484 KB correct
29 Correct 5 ms 1484 KB correct
30 Correct 9 ms 1484 KB correct
31 Correct 7 ms 1524 KB correct
32 Correct 7 ms 1484 KB correct
33 Correct 7 ms 1408 KB correct
34 Correct 1062 ms 3132 KB correct
35 Correct 1016 ms 3088 KB correct
36 Correct 708 ms 2636 KB correct
37 Correct 36 ms 1908 KB correct
38 Correct 1045 ms 3100 KB correct
39 Correct 924 ms 2940 KB correct
40 Correct 699 ms 2756 KB correct
41 Correct 1186 ms 3020 KB correct
42 Correct 1185 ms 3136 KB correct
43 Correct 316 ms 2468 KB correct
44 Correct 252 ms 2340 KB correct
45 Correct 299 ms 2496 KB correct
46 Correct 221 ms 2336 KB correct
47 Correct 100 ms 2068 KB correct
48 Correct 8 ms 1868 KB correct
49 Correct 30 ms 1916 KB correct
50 Correct 101 ms 2092 KB correct
51 Correct 300 ms 2468 KB correct
52 Correct 256 ms 2340 KB correct
53 Correct 227 ms 2340 KB correct
54 Correct 325 ms 2560 KB correct
55 Correct 309 ms 2468 KB correct
56 Correct 298 ms 2504 KB correct
57 Correct 303 ms 2512 KB correct
58 Correct 4 ms 1356 KB correct
59 Correct 4 ms 1356 KB correct
60 Execution timed out 3050 ms 5672 KB Time limit exceeded
61 Halted 0 ms 0 KB -