Submission #1124522

#	Time	Username	Problem	Language	Result	Execution time	Memory
1124522		NotLinux	Simurgh (IOI17_simurgh)	C++20	0 / 100	13 ms	3540 KiB

simurgh

#include "simurgh.h"
#include <bits/stdc++.h>
using namespace std;
#define sz(x) (int)x.size()
#define all(x) x.begin(),x.end()
const int N = 250;
int par[N];
void init(){
	iota(par , par + N , 0);
}
int find(int a){
	if(par[a] == a)return a;
	else return par[a] = find(par[a]);
}
void merge(int a , int b){
	par[find(b)] = find(a);
}
vector<int> find_roads(int n, vector<int> u, vector<int> v) {
	int m = sz(u);
	vector < pair < int , int > > bip[m];
	for(int banned = 0;banned<n;banned++){
		init();
		vector < int > r , edges;
		for(int i = 0;i<m;i++){
			if(u[i] != banned and v[i] != banned and find(u[i]) != find(v[i])){
				r.push_back(i);
				merge(u[i] , v[i]);
			}
			else if(u[i] == banned or v[i] == banned){
				edges.push_back(i);
			}
		}
		for(int i = 0;i<sz(edges)-1;i++){
			r.push_back(edges[i]);
			int result1 = count_common_roads(r);
			r.pop_back();
			r.push_back(edges[i+1]);
			int result2 = count_common_roads(r);
			r.pop_back();
			bip[edges[i]].push_back({edges[i+1] , result1 != result2});
			bip[edges[i+1]].push_back({edges[i] , result1 != result2});
		}
	}
	int vis[m] = {0};
	vector < int > ans[2];
	function<void(int,int)> dfs = [&](int node , int color){
		if(vis[node])return;
		vis[node] = 1;
		ans[color].push_back(node);
		for(auto itr : bip[node]){
			dfs(itr.first , color ^ itr.second);
		}
	};
	dfs(0,0);
	if(sz(ans[0]) == n-1)return ans[0];
	else if(sz(ans[1]) == n-1)return ans[1];
	else assert(false);
}

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