oj.uz

Submission #289405

# Submission time Handle Problem Language Result Execution time Memory
289405 2020-09-02T15:57:15 Z eohomegrownapps Simurgh (IOI17_simurgh) C++14
30 / 100
 211 ms 3192 KB 
#include "simurgh.h"
#include <bits/stdc++.h>
using namespace std;

//count_common_roads

vector<int> u;
vector<int> v;
vector<int> royal; // -1
int n;
int e;

//int count_common_roads(vector<int> &r)

struct UFDS{
	int n;
	vector<int> parent;
	UFDS(int _n){
		n = _n;
		parent.resize(n);
		for (int i = 0; i<n; i++){
			parent[i]=i;
		}
	}

	int root(int i){
		if (parent[i]==i){return i;}
		return parent[i]=root(parent[i]);
	}

	void connect(int a, int b){
		int ra = root(a);
		int rb = root(b);
		if (ra==rb){return;}
		parent[ra]=rb;
	}

	bool connected(int a, int b){
		return root(a) == root(b);
	}
};

std::vector<int> find_roads(int N, std::vector<int> U, std::vector<int> V) {
	n=N; u=U; v=V; e=u.size();
	royal.resize(e,-1);
	vector<int> ans;
	while (ans.size()<n-1){
		/*cout<<"royal: ";
		for (int i : ans){
			cout<<i<<' ';
		}cout<<endl;*/
		UFDS ufds(n);
		// add all royal roads first
		vector<int> mst;
		for (int i = 0; i<e; i++){
			if (royal[i]==1){
				mst.push_back(i);
				ufds.connect(u[i],v[i]);
			}
		}
		for (int i = 0; i<e; i++){
			if (mst.size()==n-2){
				break;
			}
			if (royal[i]==-1 && !ufds.connected(u[i],v[i])){
				mst.push_back(i);
				ufds.connect(u[i],v[i]);
			}
		}
		/*for (int i : mst){
			cout<<i<<' ';
		}cout<<endl;*/
		// try all edges
		vector<int> edges;
		vector<int> values;
		int maxval = 0;
		for (int i = 0; i<e; i++){
			if (ufds.connected(u[i],v[i])){continue;}
			// try connecting edge
			mst.push_back(i);
			values.push_back(count_common_roads(mst));
			mst.pop_back();
			edges.push_back(i);
			maxval=max(maxval,values.back());
		}
		for (int i = 0; i<edges.size(); i++){
			if (values[i]==maxval){
				royal[edges[i]]=1;
				ans.push_back(edges[i]);
			} else {
				royal[edges[i]]=0;
			}
		}
	}
	return ans;
}

Compilation message

simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:47:19: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   47 |  while (ans.size()<n-1){
      |         ~~~~~~~~~~^~~~
simurgh.cpp:62:18: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   62 |    if (mst.size()==n-2){
      |        ~~~~~~~~~~^~~~~
simurgh.cpp:86:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |   for (int i = 0; i<edges.size(); i++){
      |                   ~^~~~~~~~~~~~~

Subtask #1
13.0 / 13.0

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

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB correct
2 Correct 0 ms 256 KB correct
3 Correct 1 ms 256 KB correct
4 Correct 0 ms 256 KB correct
5 Correct 1 ms 256 KB correct
6 Correct 1 ms 256 KB correct
7 Correct 1 ms 256 KB correct
8 Correct 1 ms 256 KB correct
9 Correct 0 ms 256 KB correct
10 Correct 1 ms 256 KB correct
11 Correct 0 ms 256 KB correct
12 Correct 0 ms 256 KB correct
13 Correct 0 ms 256 KB correct
14 Correct 3 ms 384 KB correct
15 Correct 3 ms 384 KB correct
16 Correct 3 ms 384 KB correct
17 Correct 4 ms 384 KB correct
18 Correct 2 ms 384 KB correct
19 Correct 4 ms 384 KB correct
20 Correct 3 ms 384 KB correct
21 Correct 3 ms 384 KB correct
22 Correct 5 ms 384 KB correct
23 Correct 5 ms 384 KB correct
24 Correct 4 ms 384 KB correct
25 Correct 1 ms 256 KB correct
26 Correct 4 ms 384 KB correct
27 Correct 5 ms 384 KB correct
28 Correct 2 ms 384 KB correct
29 Correct 1 ms 256 KB correct
30 Correct 6 ms 384 KB correct
31 Correct 6 ms 384 KB correct
32 Correct 7 ms 384 KB correct
33 Correct 6 ms 384 KB correct

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB correct
2 Correct 0 ms 256 KB correct
3 Correct 1 ms 256 KB correct
4 Correct 0 ms 256 KB correct
5 Correct 1 ms 256 KB correct
6 Correct 1 ms 256 KB correct
7 Correct 1 ms 256 KB correct
8 Correct 1 ms 256 KB correct
9 Correct 0 ms 256 KB correct
10 Correct 1 ms 256 KB correct
11 Correct 0 ms 256 KB correct
12 Correct 0 ms 256 KB correct
13 Correct 0 ms 256 KB correct
14 Correct 3 ms 384 KB correct
15 Correct 3 ms 384 KB correct
16 Correct 3 ms 384 KB correct
17 Correct 4 ms 384 KB correct
18 Correct 2 ms 384 KB correct
19 Correct 4 ms 384 KB correct
20 Correct 3 ms 384 KB correct
21 Correct 3 ms 384 KB correct
22 Correct 5 ms 384 KB correct
23 Correct 5 ms 384 KB correct
24 Correct 4 ms 384 KB correct
25 Correct 1 ms 256 KB correct
26 Correct 4 ms 384 KB correct
27 Correct 5 ms 384 KB correct
28 Correct 2 ms 384 KB correct
29 Correct 1 ms 256 KB correct
30 Correct 6 ms 384 KB correct
31 Correct 6 ms 384 KB correct
32 Correct 7 ms 384 KB correct
33 Correct 6 ms 384 KB correct
34 Incorrect 211 ms 1280 KB WA in grader: NO
35 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB correct
2 Correct 1 ms 384 KB correct
3 Incorrect 169 ms 3192 KB WA in grader: NO
4 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB correct
2 Correct 0 ms 256 KB correct
3 Correct 1 ms 256 KB correct
4 Correct 0 ms 256 KB correct
5 Correct 1 ms 256 KB correct
6 Correct 1 ms 256 KB correct
7 Correct 1 ms 256 KB correct
8 Correct 1 ms 256 KB correct
9 Correct 0 ms 256 KB correct
10 Correct 1 ms 256 KB correct
11 Correct 0 ms 256 KB correct
12 Correct 0 ms 256 KB correct
13 Correct 0 ms 256 KB correct
14 Correct 3 ms 384 KB correct
15 Correct 3 ms 384 KB correct
16 Correct 3 ms 384 KB correct
17 Correct 4 ms 384 KB correct
18 Correct 2 ms 384 KB correct
19 Correct 4 ms 384 KB correct
20 Correct 3 ms 384 KB correct
21 Correct 3 ms 384 KB correct
22 Correct 5 ms 384 KB correct
23 Correct 5 ms 384 KB correct
24 Correct 4 ms 384 KB correct
25 Correct 1 ms 256 KB correct
26 Correct 4 ms 384 KB correct
27 Correct 5 ms 384 KB correct
28 Correct 2 ms 384 KB correct
29 Correct 1 ms 256 KB correct
30 Correct 6 ms 384 KB correct
31 Correct 6 ms 384 KB correct
32 Correct 7 ms 384 KB correct
33 Correct 6 ms 384 KB correct
34 Incorrect 211 ms 1280 KB WA in grader: NO
35 Halted 0 ms 0 KB -