Submission #559553

#	Time	Username	Problem	Language	Result	Execution time	Memory
559553		mosiashvililuka	Simurgh (IOI17_simurgh)	C++14	51 / 100	164 ms	14252 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;
pair <int, int> P[200009];
vector <int> v[200009],xe,vv[200009],VV;
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> 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;
				}
			}
			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;
		}
	}
	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> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:26:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |  for(i=0; i<Uu.size(); i++){
      |           ~^~~~~~~~~~
simurgh.cpp:79:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |     for(j=0; j<xe.size(); j++){
      |              ~^~~~~~~~~~

• Subtask 1: 13 / 13
• Subtask 2: 17 / 17
• Subtask 3: 21 / 21
• Subtask 4: 0 / 19
• Subtask 5: 0 / 30