Submission #52064

#	Time	Username	Problem	Language	Result	Execution time	Memory
52064		ernestvw	Simurgh (IOI17_simurgh)	C++11	30 / 100	862 ms	6028 KiB

simurgh

#include <bits/stdc++.h>
using namespace std;

#include "simurgh.h"
//int count_common_roads(vector<int> r);

struct Arc {
	int u, v, i;
};

int nbNodes, nbArcs;
vector<Arc> arcs;
vector<Arc> adj[501];
map<pair<int, int>, int> idx;

bool vu[501];

set<int> roads;

int oldValue = -1;
int Q=0;
int query() {
	Q++;
	if(Q > 30000) exit(1);
	vector<int> quer;
	for(int i : roads) quer.push_back(i);
	return oldValue = count_common_roads(quer);
}

void traverse(int u, int i) {
	if(vu[u]) return;
	vu[u] = 1;
	if(i != -1) roads.insert(i);
	for(Arc a : adj[u])
		if(!vu[a.v])
			traverse(a.v, a.i);
}

void buildTree() {
	for(int i = 0; i < nbNodes; i++) vu[i] = false;
	traverse(0, -1);
}

int parent[501*250];
int find(int x) {
	return x == parent[x] ? x : (parent[x] = find(parent[x]));
}
void merge(int x, int y) {
	parent[find(x)] = find(y);
}

const int ROYAL = 500*250+1;
const int BAD = 500*250+2;

bool good(int i) {
	return find(i) == find(ROYAL);	
}
bool bad(int i) {
	return find(i) == find(BAD);
}

void init() {
	for(int i = 0; i < nbArcs; i++) parent[i] = i;
	parent[ROYAL] = ROYAL;
	parent[BAD] = BAD;
}

vector<int> path, curr;
bool found=0;

void dfs(int u, int target, int p) {
	if(u == target) {
		found=1;
		path = curr;
	}
	if(found) return;
	for(Arc a : adj[u]) {
		if(!roads.count(a.i) or a.v == p) continue;
		curr.push_back(a.i);
		dfs(a.v, target, u);
		curr.pop_back();
	}
}

vector<int> findCycle(int u, int v) {
	path.clear(), curr.clear(), found=0;
	dfs(u, v, -1);
	return path;
}

void findSol() {
	init();
	for(Arc a : arcs) {
		if(roads.count(a.i)) continue;
		if(bad(a.i)) continue;
		int i = a.i;
		int u = a.u;
		int v = a.v;
		vector<int> cycle = findCycle(u, v);
		for(int id : cycle) {
			int old = oldValue;
			roads.insert(i);
			roads.erase(id);
			int nouv = query();
			if(nouv > old) {
				merge(ROYAL, i);
				merge(BAD, id);
				break;
			}
			else if(nouv == old) {
				merge(id, i);
				roads.insert(id);
				roads.erase(i);
				oldValue = old;
			}
			else {
				merge(id, ROYAL);
				merge(i, BAD);
				roads.insert(id);
				roads.erase(i);
				oldValue = old;
				break;
			}
		}
	}
}

vector<int> find_roads(int n, vector<int> u, vector<int> v) {
	nbNodes = n;
	nbArcs = (int)u.size();
	arcs.clear();
	for(int i = 0; i < nbArcs; i++) {
		arcs.push_back({u[i], v[i], i});
		adj[u[i]].push_back({u[i], v[i], i});
		adj[v[i]].push_back({v[i], u[i], i});
	}
	vector<int> ans;
	buildTree();
	query();
	findSol();
	for(int i : roads) ans.push_back(i);
	return ans;
}
/*
bool GOLDEN[501*250];
int count_common_roads(vector<int> r) {
	int cnt(0);
	for(int i:r)if(GOLDEN[i])cnt++;
	return cnt;
}

int main() {
	int T=1;
	while(T--){
	int n, m;cin>>n>>m;
	vector<int>u(m), v(m);
	for(int i=0;i<m;i++){
		cin>>u[i]>>v[i];
	}
	for(int i=0;i<m;i++)GOLDEN[i]=0;
	for(int i=0;i<n-1;i++){int s;cin>>s;GOLDEN[s]=1;}
	vector<int> sol = find_roads(n, u, v);
	for(int i : sol) {
		cout << i << " ";
	}
	cout << endl;
	}
}
*/

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