Submission #400056

#	Time	Username	Problem	Language	Result	Execution time	Memory
400056		kshitij_sodani	Simurgh (IOI17_simurgh)	C++14	51 / 100	3060 ms	8448 KiB

simurgh

//#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 (stderr)

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 / 13
• Subtask 2: 17 / 17
• Subtask 3: 21 / 21
• Subtask 4: 0 / 19
• Subtask 5: 0 / 30