oj.uz

답안 #61769

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
61769 2018-07-26T16:01:39 Z KLPP Simurgh (IOI17_simurgh) C++14
0 / 100
 3000 ms 432 KB 
#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;
}

Compilation message

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.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3033 ms 248 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3033 ms 248 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3033 ms 248 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 356 KB correct
2 Execution timed out 3031 ms 432 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3033 ms 248 KB Time limit exceeded
2 Halted 0 ms 0 KB -