Submission #814875

#	Time	Username	Problem	Language	Result	Execution time	Memory
814875		Dan4Life	Simurgh (IOI17_simurgh)	C++17	13 / 100	3067 ms	320 KiB

simurgh

#include "simurgh.h"
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
#define pb push_back
#define sz(a) (int)a.size()
const int mxN = (int)5e2+2;
const int mxM = mxN*mxN/2;
int n, m, p[mxN], sz[mxN];
bool vis[mxM];
void init(int n){ for(int i = 0; i < n; i++) p[i]=i,sz[i]=1;}
int findSet(int i){return i==p[i]?i:p[i]=findSet(p[i]);}
bool isSameSet(int i, int j){return findSet(i)==findSet(j);}
void unionSet(int i, int j){
	int x = findSet(i), y = findSet(j);
	if(x==y) return;
	if(sz[x]<sz[y]) swap(x,y);
	p[y] = x; sz[x]+=sz[y];
}

int query(vector<int> &v){
	return count_common_roads(v);
}

vi find_roads(int N, vi u, vi v) {
	vi ans; m = sz(u); n = N;
	for(int mask = 0; mask < (1<<m); mask++){
		bool ok = 1; ans.clear(); init(n);
		for(int i = 0; i < m; i++){
			if(mask>>i&1){
				if(isSameSet(u[i],v[i])) ok=0;
				unionSet(u[i],v[i]); ans.pb(i);
			}
		}
		for(int i = 0; i < n; i++) ok&=isSameSet(i,0);
		if(ok and query(ans)==n-1) return ans;
	}
}

Compilation message (stderr)

simurgh.cpp: In function 'vi find_roads(int, vi, vi)':
simurgh.cpp:38:1: warning: control reaches end of non-void function [-Wreturn-type]
   38 | }
      | ^

• Subtask 1: 13 / 13
• Subtask 2: 0 / 17
• Subtask 3: 0 / 21
• Subtask 4: 0 / 19
• Subtask 5: 0 / 30