oj.uz

Submission #61782

# Submission time Handle Problem Language Result Execution time Memory
61782 2018-07-26T16:53:17 Z KLPP Simurgh (IOI17_simurgh) C++14
30 / 100
 227 ms 4844 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){/*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]=0;
	for(int i=0;i<n;i++){
		init(n);
		int cnt=0;
		vector<int> segments;
		//cout<<i<<endl;
		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:48:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<u.size();i++){
              ~^~~~~~~~~
simurgh.cpp:53:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<u.size();i++)ans[i]=0;
              ~^~~~~~~~~
simurgh.cpp:67: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:69:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=0;j<nei[i].size();j++){
               ~^~~~~~~~~~~~~~
simurgh.cpp:73:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int k=j+1;k<nei[i].size();k++){
                   ~^~~~~~~~~~~~~~
simurgh.cpp:85:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int j=0;j<nei[i].size();j++){
                ~^~~~~~~~~~~~~~
simurgh.cpp:92:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int j=0;j<edges.size();j++){
                ~^~~~~~~~~~~~~
simurgh.cpp:56:7: warning: unused variable 'cnt' [-Wunused-variable]
   int cnt=0;
       ^~~
simurgh.cpp:100:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<u.size();i++){
              ~^~~~~~~~~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB correct
2 Correct 4 ms 488 KB correct
3 Correct 4 ms 488 KB correct
4 Correct 3 ms 488 KB correct
5 Correct 2 ms 504 KB correct
6 Correct 3 ms 632 KB correct
7 Correct 3 ms 632 KB correct
8 Correct 3 ms 632 KB correct
9 Correct 2 ms 632 KB correct
10 Correct 3 ms 632 KB correct
11 Correct 3 ms 632 KB correct
12 Correct 4 ms 632 KB correct
13 Correct 2 ms 632 KB correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB correct
2 Correct 4 ms 488 KB correct
3 Correct 4 ms 488 KB correct
4 Correct 3 ms 488 KB correct
5 Correct 2 ms 504 KB correct
6 Correct 3 ms 632 KB correct
7 Correct 3 ms 632 KB correct
8 Correct 3 ms 632 KB correct
9 Correct 2 ms 632 KB correct
10 Correct 3 ms 632 KB correct
11 Correct 3 ms 632 KB correct
12 Correct 4 ms 632 KB correct
13 Correct 2 ms 632 KB correct
14 Correct 8 ms 636 KB correct
15 Correct 7 ms 644 KB correct
16 Correct 8 ms 652 KB correct
17 Correct 7 ms 660 KB correct
18 Correct 4 ms 668 KB correct
19 Correct 6 ms 672 KB correct
20 Correct 5 ms 680 KB correct
21 Correct 5 ms 688 KB correct
22 Correct 5 ms 688 KB correct
23 Correct 5 ms 720 KB correct
24 Correct 6 ms 740 KB correct
25 Correct 5 ms 740 KB correct
26 Correct 5 ms 748 KB correct
27 Correct 5 ms 752 KB correct
28 Correct 3 ms 856 KB correct
29 Correct 3 ms 856 KB correct
30 Correct 5 ms 856 KB correct
31 Correct 5 ms 856 KB correct
32 Correct 6 ms 856 KB correct
33 Correct 6 ms 856 KB correct

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB correct
2 Correct 4 ms 488 KB correct
3 Correct 4 ms 488 KB correct
4 Correct 3 ms 488 KB correct
5 Correct 2 ms 504 KB correct
6 Correct 3 ms 632 KB correct
7 Correct 3 ms 632 KB correct
8 Correct 3 ms 632 KB correct
9 Correct 2 ms 632 KB correct
10 Correct 3 ms 632 KB correct
11 Correct 3 ms 632 KB correct
12 Correct 4 ms 632 KB correct
13 Correct 2 ms 632 KB correct
14 Correct 8 ms 636 KB correct
15 Correct 7 ms 644 KB correct
16 Correct 8 ms 652 KB correct
17 Correct 7 ms 660 KB correct
18 Correct 4 ms 668 KB correct
19 Correct 6 ms 672 KB correct
20 Correct 5 ms 680 KB correct
21 Correct 5 ms 688 KB correct
22 Correct 5 ms 688 KB correct
23 Correct 5 ms 720 KB correct
24 Correct 6 ms 740 KB correct
25 Correct 5 ms 740 KB correct
26 Correct 5 ms 748 KB correct
27 Correct 5 ms 752 KB correct
28 Correct 3 ms 856 KB correct
29 Correct 3 ms 856 KB correct
30 Correct 5 ms 856 KB correct
31 Correct 5 ms 856 KB correct
32 Correct 6 ms 856 KB correct
33 Correct 6 ms 856 KB correct
34 Incorrect 227 ms 2164 KB WA in grader: NO
35 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2164 KB correct
2 Correct 2 ms 2164 KB correct
3 Incorrect 179 ms 4844 KB WA in grader: NO
4 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB correct
2 Correct 4 ms 488 KB correct
3 Correct 4 ms 488 KB correct
4 Correct 3 ms 488 KB correct
5 Correct 2 ms 504 KB correct
6 Correct 3 ms 632 KB correct
7 Correct 3 ms 632 KB correct
8 Correct 3 ms 632 KB correct
9 Correct 2 ms 632 KB correct
10 Correct 3 ms 632 KB correct
11 Correct 3 ms 632 KB correct
12 Correct 4 ms 632 KB correct
13 Correct 2 ms 632 KB correct
14 Correct 8 ms 636 KB correct
15 Correct 7 ms 644 KB correct
16 Correct 8 ms 652 KB correct
17 Correct 7 ms 660 KB correct
18 Correct 4 ms 668 KB correct
19 Correct 6 ms 672 KB correct
20 Correct 5 ms 680 KB correct
21 Correct 5 ms 688 KB correct
22 Correct 5 ms 688 KB correct
23 Correct 5 ms 720 KB correct
24 Correct 6 ms 740 KB correct
25 Correct 5 ms 740 KB correct
26 Correct 5 ms 748 KB correct
27 Correct 5 ms 752 KB correct
28 Correct 3 ms 856 KB correct
29 Correct 3 ms 856 KB correct
30 Correct 5 ms 856 KB correct
31 Correct 5 ms 856 KB correct
32 Correct 6 ms 856 KB correct
33 Correct 6 ms 856 KB correct
34 Incorrect 227 ms 2164 KB WA in grader: NO
35 Halted 0 ms 0 KB -