oj.uz

Submission #400056

# Submission time Handle Problem Language Result Execution time Memory
400056 2021-05-07T09:31:02 Z kshitij_sodani Simurgh (IOI17_simurgh) C++14
51 / 100
 3000 ms 8448 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 act[513*513];
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 and act[j.b]){
			pp.pb(j.b);
			dfs(j.a,no);
			pp.pop_back();
		}
	}
}
vector<int> ans2;
vector<int> ans;
int count2=0;
vector<int> zz5;
int ask2(vector<pair<int,int>> cur){
	for(int i=0;i<n;i++){
		adj[i].clear();
	}
	for(auto i:zz5){
		if(tt[i]==0){
			adj[uu[i]].pb({vv[i],i});
			adj[vv[i]].pb({uu[i],i});
			act[i]=1;
		}
	}
	for(auto j:cur){
		act[ind5[j.a][j.b]]=0;
		adj[j.a].pb({j.b,ind5[j.a][j.b]});
		adj[j.b].pb({j.a,ind5[j.a][j.b]});	
	}
	for(auto j:cur){
		ca=j.b;
		dfs(j.a);
		for(auto i:pp2){
			if(tt[i]==0){
				act[i]=0;
				act[ind5[j.a][j.b]]=1;
				vector<int> ff={uu[i],vv[i]};
			/*	for(auto ii:ff){
					//if(uu[i]==ii or vv[i]==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 and act[j.b]){
				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--;
				//cout<<j<<"<<"<<endl;
			}
		}
	}
	/*cout<<xx<<endl;
	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;
			zz5.pb(i);
			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(int i=0;i<m;i++){
		act[i]=1;
	}

	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;*/

	}
	for(int i=0;i<m;i++){
		act[i]=0;
	}
	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 'void solve(std::vector<std::pair<int, int> >, int)':
simurgh.cpp:179: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]
  179 |   for(int i=0;i<xx.size()/2;i++){
      |               ~^~~~~~~~~~~~
simurgh.cpp:182: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]
  182 |   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:305: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]
  305 |    for(int i=0;i<xx.size();i++){
      |                ~^~~~~~~~~~
simurgh.cpp:391:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  391 |    for(int k=0;k<bb.size();k++){
      |                ~^~~~~~~~~~
simurgh.cpp:400:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  400 |    for(int k=0;k<aa.size();k++){
      |                ~^~~~~~~~~~
simurgh.cpp:401:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  401 |     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 1356 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 1432 KB correct
6 Correct 5 ms 1356 KB correct
7 Correct 4 ms 1356 KB correct
8 Correct 4 ms 1356 KB correct
9 Correct 4 ms 1356 KB correct
10 Correct 4 ms 1356 KB correct
11 Correct 4 ms 1356 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 1356 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 1432 KB correct
6 Correct 5 ms 1356 KB correct
7 Correct 4 ms 1356 KB correct
8 Correct 4 ms 1356 KB correct
9 Correct 4 ms 1356 KB correct
10 Correct 4 ms 1356 KB correct
11 Correct 4 ms 1356 KB correct
12 Correct 4 ms 1356 KB correct
13 Correct 4 ms 1356 KB correct
14 Correct 8 ms 1484 KB correct
15 Correct 8 ms 1484 KB correct
16 Correct 9 ms 1560 KB correct
17 Correct 8 ms 1484 KB correct
18 Correct 6 ms 1484 KB correct
19 Correct 7 ms 1552 KB correct
20 Correct 7 ms 1484 KB correct
21 Correct 7 ms 1484 KB correct
22 Correct 6 ms 1484 KB correct
23 Correct 6 ms 1484 KB correct
24 Correct 5 ms 1484 KB correct
25 Correct 4 ms 1484 KB correct
26 Correct 7 ms 1484 KB correct
27 Correct 6 ms 1484 KB correct
28 Correct 5 ms 1484 KB correct
29 Correct 5 ms 1484 KB correct
30 Correct 5 ms 1484 KB correct
31 Correct 6 ms 1476 KB correct
32 Correct 6 ms 1456 KB correct
33 Correct 6 ms 1484 KB correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1356 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 1432 KB correct
6 Correct 5 ms 1356 KB correct
7 Correct 4 ms 1356 KB correct
8 Correct 4 ms 1356 KB correct
9 Correct 4 ms 1356 KB correct
10 Correct 4 ms 1356 KB correct
11 Correct 4 ms 1356 KB correct
12 Correct 4 ms 1356 KB correct
13 Correct 4 ms 1356 KB correct
14 Correct 8 ms 1484 KB correct
15 Correct 8 ms 1484 KB correct
16 Correct 9 ms 1560 KB correct
17 Correct 8 ms 1484 KB correct
18 Correct 6 ms 1484 KB correct
19 Correct 7 ms 1552 KB correct
20 Correct 7 ms 1484 KB correct
21 Correct 7 ms 1484 KB correct
22 Correct 6 ms 1484 KB correct
23 Correct 6 ms 1484 KB correct
24 Correct 5 ms 1484 KB correct
25 Correct 4 ms 1484 KB correct
26 Correct 7 ms 1484 KB correct
27 Correct 6 ms 1484 KB correct
28 Correct 5 ms 1484 KB correct
29 Correct 5 ms 1484 KB correct
30 Correct 5 ms 1484 KB correct
31 Correct 6 ms 1476 KB correct
32 Correct 6 ms 1456 KB correct
33 Correct 6 ms 1484 KB correct
34 Correct 315 ms 3216 KB correct
35 Correct 301 ms 3176 KB correct
36 Correct 212 ms 2764 KB correct
37 Correct 20 ms 1956 KB correct
38 Correct 325 ms 3200 KB correct
39 Correct 269 ms 3016 KB correct
40 Correct 205 ms 2808 KB correct
41 Correct 352 ms 3252 KB correct
42 Correct 354 ms 3252 KB correct
43 Correct 99 ms 2608 KB correct
44 Correct 87 ms 2480 KB correct
45 Correct 96 ms 2580 KB correct
46 Correct 71 ms 2356 KB correct
47 Correct 37 ms 2000 KB correct
48 Correct 7 ms 1868 KB correct
49 Correct 16 ms 1960 KB correct
50 Correct 35 ms 1996 KB correct
51 Correct 93 ms 2580 KB correct
52 Correct 84 ms 2488 KB correct
53 Correct 73 ms 2408 KB correct
54 Correct 102 ms 2620 KB correct
55 Correct 90 ms 2584 KB correct
56 Correct 90 ms 2468 KB correct
57 Correct 94 ms 2592 KB correct

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1300 KB correct
2 Correct 5 ms 1356 KB correct
3 Correct 1363 ms 6056 KB correct
4 Correct 2804 ms 8380 KB correct
5 Correct 2807 ms 8332 KB correct
6 Execution timed out 3060 ms 8448 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1356 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 1432 KB correct
6 Correct 5 ms 1356 KB correct
7 Correct 4 ms 1356 KB correct
8 Correct 4 ms 1356 KB correct
9 Correct 4 ms 1356 KB correct
10 Correct 4 ms 1356 KB correct
11 Correct 4 ms 1356 KB correct
12 Correct 4 ms 1356 KB correct
13 Correct 4 ms 1356 KB correct
14 Correct 8 ms 1484 KB correct
15 Correct 8 ms 1484 KB correct
16 Correct 9 ms 1560 KB correct
17 Correct 8 ms 1484 KB correct
18 Correct 6 ms 1484 KB correct
19 Correct 7 ms 1552 KB correct
20 Correct 7 ms 1484 KB correct
21 Correct 7 ms 1484 KB correct
22 Correct 6 ms 1484 KB correct
23 Correct 6 ms 1484 KB correct
24 Correct 5 ms 1484 KB correct
25 Correct 4 ms 1484 KB correct
26 Correct 7 ms 1484 KB correct
27 Correct 6 ms 1484 KB correct
28 Correct 5 ms 1484 KB correct
29 Correct 5 ms 1484 KB correct
30 Correct 5 ms 1484 KB correct
31 Correct 6 ms 1476 KB correct
32 Correct 6 ms 1456 KB correct
33 Correct 6 ms 1484 KB correct
34 Correct 315 ms 3216 KB correct
35 Correct 301 ms 3176 KB correct
36 Correct 212 ms 2764 KB correct
37 Correct 20 ms 1956 KB correct
38 Correct 325 ms 3200 KB correct
39 Correct 269 ms 3016 KB correct
40 Correct 205 ms 2808 KB correct
41 Correct 352 ms 3252 KB correct
42 Correct 354 ms 3252 KB correct
43 Correct 99 ms 2608 KB correct
44 Correct 87 ms 2480 KB correct
45 Correct 96 ms 2580 KB correct
46 Correct 71 ms 2356 KB correct
47 Correct 37 ms 2000 KB correct
48 Correct 7 ms 1868 KB correct
49 Correct 16 ms 1960 KB correct
50 Correct 35 ms 1996 KB correct
51 Correct 93 ms 2580 KB correct
52 Correct 84 ms 2488 KB correct
53 Correct 73 ms 2408 KB correct
54 Correct 102 ms 2620 KB correct
55 Correct 90 ms 2584 KB correct
56 Correct 90 ms 2468 KB correct
57 Correct 94 ms 2592 KB correct
58 Correct 4 ms 1300 KB correct
59 Correct 5 ms 1356 KB correct
60 Correct 1363 ms 6056 KB correct
61 Correct 2804 ms 8380 KB correct
62 Correct 2807 ms 8332 KB correct
63 Execution timed out 3060 ms 8448 KB Time limit exceeded
64 Halted 0 ms 0 KB -