제출 #61769

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
61769		KLPP	Simurgh (IOI17_simurgh)	C++14	0 / 100	3033 ms	432 KiB

simurgh

#include "simurgh.h"
#include<vector>
#include<iostream>
#include<algorithm>
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){
	if(parent[a]!=a)a=root(a);
	if(parent[b]!=b)b=root(b);
	if(a==b)return;
	if(size[a]<size[b]){
		parent[a]=b;
		size[b]+=size[a];
	}
	parent[b]=a;
	size[a]+=size[b];
}
bool samecomponent(int a, int b){
	if(parent[a]!=a)a=root(a);
	if(parent[b]!=b)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]=0;
	for(int i=0;i<n;i++){
		init(n);
		int cnt=0;
		vector<int> segments;
		for(unsigned int j=0;j<u.size();j++){
			if(u[j]!=i && v[j]!=i && !samecomponent(u[j],v[j])){
				segments.push_back(j);
				merge(u[j],v[j]);
			}
		}
		int CC[nei[i].size()];
		vector<int> Positions;
		for(int j=0;j<nei[i].size();j++)CC[j]=-1;
		int count=0;
		for(int j=0;j<nei[i].size();j++){
			if(CC[j]==-1){
				CC[j]=count;
				Positions.push_back(segments.size());
				for(int k=j+1;k<nei[i].size();k++){
					if(samecomponent(nei[i][j].first,nei[i][k].first)){
						CC[k]=count;
					}
				}count++;
				segments.push_back(nei[i][j].second);
			}
		}//cout<<count<<endl;
		/*for(int j=0;j<nei[i].size();j++)cout<<CC[j]<<" ";
		cout<<endl;*/
		for(int h=0;h<count;h++){
			vector<pair<int,int> >edges;
			for(int j=0;j<nei[i].size();j++){
				if(CC[j]==h){
					segments[Positions[h]]=nei[i][j].second;
					edges.push_back(pair<int,int>(count_common_roads(segments),nei[i][j].second));
				}
			}
			sort(edges.begin(),edges.end());
			for(int j=0;j<edges.size();j++){
				if(edges[j].first==edges[edges.size()-1].first){
					ans[edges[j].second]=1;
				}
			}
		}
	}
	vector<int> r;
	for(int i=0;i<u.size();i++){
		if(ans[i])r.push_back(i);
	}
	return r;
}

컴파일 시 표준 에러 (stderr) 메시지

simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:38:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<u.size();i++){
              ~^~~~~~~~~
simurgh.cpp:43:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<u.size();i++)ans[i]=0;
              ~^~~~~~~~~
simurgh.cpp:56:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=0;j<nei[i].size();j++)CC[j]=-1;
               ~^~~~~~~~~~~~~~
simurgh.cpp:58:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=0;j<nei[i].size();j++){
               ~^~~~~~~~~~~~~~
simurgh.cpp:62:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int k=j+1;k<nei[i].size();k++){
                   ~^~~~~~~~~~~~~~
simurgh.cpp:74:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int j=0;j<nei[i].size();j++){
                ~^~~~~~~~~~~~~~
simurgh.cpp:81:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int j=0;j<edges.size();j++){
                ~^~~~~~~~~~~~~
simurgh.cpp:46:7: warning: unused variable 'cnt' [-Wunused-variable]
   int cnt=0;
       ^~~
simurgh.cpp:89:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<u.size();i++){
              ~^~~~~~~~~

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