Submission #137362

#	Time	Username	Problem	Language	Result	Execution time	Memory
137362		wilwxk	Simurgh (IOI17_simurgh)	C++14	0 / 100	2 ms	380 KiB

simurgh

#include "simurgh.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int MAXN=502;
int aresta[MAXN*MAXN][2];
vector<int> g[MAXN], gt[MAXN];
int rep[MAXN], tam[MAXN];
vector<int> config;
vector<int> respf;
bool usado[MAXN*MAXN], bom[MAXN];
int n, m;
bool debug=0;

int find(int cur) {
	if(rep[cur]==cur) return cur;
	return rep[cur]=find(rep[cur]);
}
void une(int a, int b) {
	a=find(a); b=find(b);
	if(a==b) return;
	if(tam[a]<tam[b]) swap(a, b);
	rep[a]=b;
}
void geradora() {
	srand(time(0)+n+m);
	for(int i=0; i<n; i++) rep[i]=i, tam[i]=i;
	for(int i=0; i<m; i++) {
		int a=aresta[i][0]; int b=aresta[i][1];
		if(find(a)==find(b)) continue;
		gt[a].push_back(i);
		gt[b].push_back(i);
		une(a, b);
		if(debug) printf("tree:: %d %d // %d\n", a, b, i);
	}
}

int query() {
	if(debug){for(auto cur : config) printf("%d ", cur); cout << ">> " << count_common_roads(config) << endl;}
	for(int i=0; i<n; i++) rep[i]=i;
	for(auto cur : config) une(aresta[cur][0], aresta[cur][1]);
	for(int i=0; i<n; i++) if(find(i)!=find(0)) return MAXN;
	return count_common_roads(config);
}

void solve(int cur, int pid) {
	random_shuffle(g[cur].begin(), g[cur].end());

	int ori=query();
	vector<int> aux; aux=config; config.clear();
	for(auto cur : aux) if(cur!=pid) config.push_back(cur);
	config.push_back(pid);

	if(g[cur].size()==1) {
		respf.push_back(pid);
		bom[pid]=1;
		return;
	}
	for(auto vid : g[cur]) {
		if(vid==pid||bom[vid]||usado[vid]) continue;
		config.pop_back();
		config.push_back(vid);
		int val=query();
		config.pop_back();
		config.push_back(pid);

		if(val!=ori) {
			if(val<ori) respf.push_back(pid), bom[pid]=1;
			else respf.push_back(vid), bom[vid]=1;
			break;
		}
	}
	if(debug) printf("solved %d\n", respf.back());
}

void predfs(int cur, int pid) {
	if(pid!=-1) config.push_back(pid), usado[pid]=1	;
	for(auto vid : gt[cur]) {
		if(vid==pid) continue;
		int viz= aresta[vid][aresta[vid][0]==cur];
		predfs(viz, vid);
	}
	if(pid==-1) return;
}
void dfs(int cur, int pid) {
	if(debug) printf("dfs %d %d\n", cur, pid);
	for(auto vid : gt[cur]) {
		if(vid==pid) continue;
		int viz= aresta[vid][aresta[vid][0]==cur];
		dfs(viz, vid);
	}
	if(pid==-1) return;
	solve(cur, pid);
}

std::vector<int> find_roads(int N, std::vector<int> U, std::vector<int> V) {
	n=N; m=U.size();
	for(int i=0; i<m; i++) {
		int a=U[i]; int b=V[i];
		aresta[i][0]=a; aresta[i][1]=b;
		g[a].push_back(i);
		g[b].push_back(i);
	}

	geradora();
	predfs(0, -1);
	dfs(0, -1);

	if(debug) for(auto cur : respf) printf("%d ", cur);
	return respf;
}

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