Submission #71523

#	Time	Username	Problem	Language	Result	Execution time	Memory
71523		KLPP	Simurgh (IOI17_simurgh)	C++14	51 / 100	348 ms	7208 KiB

simurgh

#include "simurgh.h"
#include<vector>
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
typedef pair<int,int> pi;
vector<pi> nei[100];
int parent[500];
int size[500];
void init(int n){
	for(int i=0;i<n;i++){
		size[i]=1;parent[i]=i;
	}
}
int root(int a){
	if(parent[a]==a)return a;
	return root(parent[a]);
}
void merge(int a, int b){/*cout<<a<<" "<<b<<endl;
	for(int i=0;i<7;i++)cout<<parent[i]<<" ";
	cout<<endl;
	for(int i=0;i<7;i++)cout<<size[i]<<" ";
	cout<<endl<<endl;*/
	a=root(a);
	b=root(b);
	if(a==b)return;
	if(size[a]<size[b]){
		parent[a]=b;
		size[b]+=size[a];
		return;
	}
	parent[b]=a;
	size[a]+=size[b];
}
bool samecomponent(int a, int b){/*cout<<a<<" "<<b<<endl;
	for(int i=0;i<7;i++)cout<<parent[i]<<" ";
	cout<<endl;
	for(int i=0;i<7;i++)cout<<size[i]<<" ";
	cout<<endl<<endl;*/
	a=root(a);
	b=root(b);
	if(a==b)return true;
	return false;
}
std::vector<int> find_roads(int n, std::vector<int> u, std::vector<int> v) {
	vector<pair<int,int> >nei[n];
	
	for(int i=0;i<u.size();i++){
		nei[u[i]].push_back(pair<int,int>(v[i],i));
		nei[v[i]].push_back(pair<int,int>(u[i],i));
	}
	int ans[u.size()];
	for(int i=0;i<u.size();i++)ans[i]=-1;
	vector<pair<int,int> >tree[n];
	init(n);
	bool istree[u.size()];
	vector<int> maintree;
	for(int i=0;i<u.size();i++){istree[i]=false;
		if(!samecomponent(u[i],v[i])){istree[i]=true;
			merge(u[i],v[i]);
			tree[u[i]].push_back(pair<int,int>(v[i],i));
			tree[v[i]].push_back(pair<int,int>(u[i],i));
			//cout<<i<<endl;
			maintree.push_back(i);
		}
	}
	int s=count_common_roads(maintree);
	for(int i=0;i<u.size();i++){
		if(!istree[i]){
			queue<int> q;
			int dist[n];
			for(int i=0;i<n;i++)dist[i]=-1;
			dist[u[i]]=0;
			q.push(u[i]);
			while(!q.empty()){
				int node=q.front();q.pop();
				for(int j=0;j<tree[node].size();j++){
					int V=tree[node][j].first;
					if(dist[V]==-1){
						dist[V]=dist[node]+1;
						q.push(V);
					}
				}
			}
			vector<int> edges;
			int pnt=v[i];
			while(dist[pnt]!=0){
				for(int j=0;j<tree[pnt].size();j++){
					int node=tree[pnt][j].first;
					if(dist[node]<dist[pnt]){
						edges.push_back(tree[pnt][j].second);
						pnt=node;
						j=10000;
					}
				}
			}//OK
			/*cout<<"Edge no "<<i<<" : ";
			for(int j=0;j<edges.size();j++)cout<<edges[j]<<" ";
			cout<<endl;*/
			vector<int> indeterminado;
			vector<int> determinado;
			for(int j=0;j<edges.size();j++){
				if(ans[edges[j]]==-1)indeterminado.push_back(edges[j]);
				else determinado.push_back(edges[j]);
			}
			if(determinado.size()==0){
				vector<pair<int,int> >respostas;
				for(int j=0;j<edges.size();j++){
					int lo,hi;
					lo=-1;
					hi=n;
					while(hi-lo>1){
						int mid=(hi+lo)/2;
						if(maintree[mid]<edges[j])lo=mid;
						else hi=mid;
					}
					maintree[hi]=i;
					int A=count_common_roads(maintree);
					respostas.push_back(pair<int,int>(A,edges[j]));
					maintree[hi]=edges[j];
				}
				respostas.push_back(pair<int,int>(s,i));
				sort(respostas.begin(),respostas.end());
				
				/*for(int j=0;j<respostas.size();j++){
					cout<<respostas[j].first<<" ";
				}cout<<endl;
				for(int j=0;j<respostas.size();j++){
					cout<<respostas[j].second<<" ";
				}cout<<endl;*/
				if(respostas[0].first==respostas[respostas.size()-1].first){
					for(int j=0;j<respostas.size();j++){
						ans[respostas[j].second]=0;
					}
				}else{
					for(int j=0;j<respostas.size();j++){ans[respostas[j].second]=0;
						if(respostas[j].first==respostas[0].first){
							ans[respostas[j].second]=1;
						}
					}
				}
			}else{	
				
				vector<pair<int,int> >respostas;
				for(int j=0;j<indeterminado.size();j++){//cout<<indeterminado[j]<<" "<<ans[indeterminado[j]]<<endl;
					int lo,hi;
					lo=-1;
					hi=n;
					while(hi-lo>1){
						int mid=(hi+lo)/2;
						if(maintree[mid]<indeterminado[j])lo=mid;
						else hi=mid;
					}//cout<<maintree[hi]<<" "<<indeterminado[j]<<endl;
					maintree[hi]=i;
					/*for(int i=0;i<n-1;i++){
						cout<<maintree[i]<<" ";
					}cout<<endl;*/
					int A=count_common_roads(maintree);
					//cout<<A<<endl;
					respostas.push_back(pair<int,int>(A,indeterminado[j]));
					maintree[hi]=indeterminado[j];
				}//cout<<endl;
				respostas.push_back(pair<int,int>(s,i));
				//cout<<determinado[0]<<" "<<indeterminado.size()<<endl;
				int lo,hi;
				lo=-1;
				hi=n;
				while(hi-lo>1){
					int mid=(hi+lo)/2;
					if(maintree[mid]<determinado[0])lo=mid;
					else hi=mid;
				}
				maintree[hi]=i;
				int reference=count_common_roads(maintree);
				maintree[hi]=determinado[0];
				for(int j=0;j<respostas.size();j++){//cout<<respostas[j].first<<" "<<respostas[j].second<<endl;
					ans[respostas[j].second]=ans[determinado[0]]+reference-respostas[j].first;
				}
			}
		}
		/*cout<<i<<endl;
		for(int i=0;i<u.size();i++){
			cout<<ans[i]<<" ";
		}cout<<endl;
		for(int i=0;i<n-1;i++){
			cout<<maintree[i]<<" ";
		}cout<<endl;*/
	}
	/*for(int i=0;i<u.size();i++){
		cout<<ans[i]<<" ";
	}cout<<endl;*/
	
	vector<int> r;
	for(int i=0;i<u.size();i++){
		if(ans[i]!=0)r.push_back(i);
	}
	return r;
}

Compilation message (stderr)

simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:49:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<u.size();i++){
              ~^~~~~~~~~
simurgh.cpp:54:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<u.size();i++)ans[i]=-1;
              ~^~~~~~~~~
simurgh.cpp:59:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<u.size();i++){istree[i]=false;
              ~^~~~~~~~~
simurgh.cpp:69:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<u.size();i++){
              ~^~~~~~~~~
simurgh.cpp:78:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int j=0;j<tree[node].size();j++){
                 ~^~~~~~~~~~~~~~~~~~
simurgh.cpp:89:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int j=0;j<tree[pnt].size();j++){
                 ~^~~~~~~~~~~~~~~~~
simurgh.cpp:103:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int j=0;j<edges.size();j++){
                ~^~~~~~~~~~~~~
simurgh.cpp:109:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int j=0;j<edges.size();j++){
                 ~^~~~~~~~~~~~~
simurgh.cpp:133:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
      for(int j=0;j<respostas.size();j++){
                  ~^~~~~~~~~~~~~~~~~
simurgh.cpp:137:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
      for(int j=0;j<respostas.size();j++){ans[respostas[j].second]=0;
                  ~^~~~~~~~~~~~~~~~~
simurgh.cpp:146:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int j=0;j<indeterminado.size();j++){//cout<<indeterminado[j]<<" "<<ans[indeterminado[j]]<<endl;
                 ~^~~~~~~~~~~~~~~~~~~~~
simurgh.cpp:177:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int j=0;j<respostas.size();j++){//cout<<respostas[j].first<<" "<<respostas[j].second<<endl;
                 ~^~~~~~~~~~~~~~~~~
simurgh.cpp:195:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<u.size();i++){
              ~^~~~~~~~~

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