oj.uz

Submission #519680

# Submission time Handle Problem Language Result Execution time Memory
519680 2022-01-27T03:22:54 Z rilakkuma Simurgh (IOI17_simurgh) C++14
13 / 100
 20 ms 304 KB 
#include "simurgh.h"
#include <bits/stdc++.h>
using namespace std;

// count_common_roads(vector<int> &r)

// * COMMENT THIS LATER
// int count_common_roads(vector<int> &r){
// 	cout << "? "; 
// 	for(int x : r) cout << x << " ";
// 	cout << endl;
// 	int res; cin >> res;
// 	return res;
// }

int par[505];
int get(int u) { return u == par[u] ? u : par[u] = get(par[u]); }
void merge(int u, int v) { par[get(u)] = get(v); }

bool connected(int n, int &mask, vector<int> &u, vector<int> &v) {
	for(int i=0; i<n; i++) par[i] = i;
	for(int i=0; i<u.size(); i++){
		if((mask >> i) & 1){
			merge(u[i], v[i]);
		}
	}

	int res = 0;
	for(int i=0; i<n; i++) res += (get(i) == get(0));
	return res == n;
}


std::vector<int> find_roads(int n, std::vector<int> u, std::vector<int> v) {
	std::vector<int> r(n - 1);
	int m = u.size();
	for(int mask=0; mask<(1<<m); mask++){
		if(__builtin_popcount(mask) == n-1){
			if(connected(n, mask, u, v)){
				r.clear();
				for(int i=0; i<m; i++)
					if((mask >> i) & 1) r.push_back(i);
				int res = count_common_roads(r);
				if(res == n-1) return r;
			}
		}
	}
	return vector<int>();
}


// * COMMENT THIS LATER
// int main(){
// 	int n, m; cin >> n >> m;
// 	vector<int> u(m), v(m);
// 	for(int i=0; i<m; i++){
// 		cin >> u[i] >> v[i];
// 	}
// 	vector<int> ans = find_roads(n, u, v);
// 	cout << "! "; for(int x : ans) cout << x << " ";
// 	cout << endl;
// }

/*
sample
4 6
0 1
0 2
0 3
1 2
1 3
2 3
*/

Compilation message

simurgh.cpp: In function 'bool connected(int, int&, std::vector<int>&, std::vector<int>&)':
simurgh.cpp:22:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |  for(int i=0; i<u.size(); i++){
      |               ~^~~~~~~~~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 208 KB correct
2 Correct 16 ms 296 KB correct
3 Correct 20 ms 300 KB correct
4 Correct 1 ms 208 KB correct
5 Correct 1 ms 208 KB correct
6 Correct 2 ms 300 KB correct
7 Correct 0 ms 208 KB correct
8 Correct 0 ms 300 KB correct
9 Correct 0 ms 296 KB correct
10 Correct 1 ms 208 KB correct
11 Correct 1 ms 208 KB correct
12 Correct 1 ms 208 KB correct
13 Correct 8 ms 304 KB correct

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 208 KB correct
2 Correct 16 ms 296 KB correct
3 Correct 20 ms 300 KB correct
4 Correct 1 ms 208 KB correct
5 Correct 1 ms 208 KB correct
6 Correct 2 ms 300 KB correct
7 Correct 0 ms 208 KB correct
8 Correct 0 ms 300 KB correct
9 Correct 0 ms 296 KB correct
10 Correct 1 ms 208 KB correct
11 Correct 1 ms 208 KB correct
12 Correct 1 ms 208 KB correct
13 Correct 8 ms 304 KB correct
14 Incorrect 1 ms 208 KB WA in grader: NO
15 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 208 KB correct
2 Correct 16 ms 296 KB correct
3 Correct 20 ms 300 KB correct
4 Correct 1 ms 208 KB correct
5 Correct 1 ms 208 KB correct
6 Correct 2 ms 300 KB correct
7 Correct 0 ms 208 KB correct
8 Correct 0 ms 300 KB correct
9 Correct 0 ms 296 KB correct
10 Correct 1 ms 208 KB correct
11 Correct 1 ms 208 KB correct
12 Correct 1 ms 208 KB correct
13 Correct 8 ms 304 KB correct
14 Incorrect 1 ms 208 KB WA in grader: NO
15 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 296 KB correct
2 Incorrect 1 ms 208 KB WA in grader: NO
3 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 208 KB correct
2 Correct 16 ms 296 KB correct
3 Correct 20 ms 300 KB correct
4 Correct 1 ms 208 KB correct
5 Correct 1 ms 208 KB correct
6 Correct 2 ms 300 KB correct
7 Correct 0 ms 208 KB correct
8 Correct 0 ms 300 KB correct
9 Correct 0 ms 296 KB correct
10 Correct 1 ms 208 KB correct
11 Correct 1 ms 208 KB correct
12 Correct 1 ms 208 KB correct
13 Correct 8 ms 304 KB correct
14 Incorrect 1 ms 208 KB WA in grader: NO
15 Halted 0 ms 0 KB -