Submission #519680

#	Time	Username	Problem	Language	Result	Execution time	Memory
519680		rilakkuma	Simurgh (IOI17_simurgh)	C++14	13 / 100	20 ms	304 KiB

simurgh

#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 (stderr)

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 / 13
• Subtask 2: 0 / 17
• Subtask 3: 0 / 21
• Subtask 4: 0 / 19
• Subtask 5: 0 / 30