Submission #559600

#	Time	Username	Problem	Language	Result	Execution time	Memory
559600		mosiashvililuka	Simurgh (IOI17_simurgh)	C++14	100 / 100	202 ms	16364 KiB

simurgh

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

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