Submission #52073

#	Time	Username	Problem	Language	Result	Execution time	Memory
52073		ernestvw	Simurgh (IOI17_simurgh)	C++11	0 / 100	9 ms	6372 KiB

simurgh

/*
	Time: O(N^4)
	Queries: Q <= 30000
	Score: 30/100
*/
#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 query() {
	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;
}

map<pair<int, int>, int> memo;
int Query(int id1, int id2) {
	if(memo.count({id1, id2})) {
		oldValue += memo[{id1, id2}];
		return oldValue;
	}
	else {
		int queee(-1);
		if(find(id1) == find(id2)) queee = oldValue;
		else queee = query();
		int tmp = oldValue;
		memo[{id1, id2}] = memo[{id2, id1}] = queee - tmp;
		return queee;
	}
}

int rev[501*250];
int devient(int x){return x==rev[x]?x:(rev[x]=devient(rev[x]));}
void fusion(int x, int y){rev[devient(x)]=devient(y);}

vector<int> act;
vector<int> Path[501][501];
void Dfs(int u, int p, int anc) {
	if(vu[u])return;
	Path[anc][u] = act;
	for(Arc a : adj[u]) {
		if(!roads.count(a.i) or a.v == p) continue;
		act.push_back(a.i);
		Dfs(a.v, u, anc);
		act.pop_back();
	}
}
void initTree() {
	for(int i = 0; i < nbArcs; i++) rev[i] = i;
	for(int i = 0; i < nbNodes; i++) {
		for(int j = 0; j < nbNodes; j++) vu[j] = 0;
		act.clear();
		Dfs(i, -1, i);
	}
}
vector<int> findCycle2(int u, int v) {
	vector<int> cycle;set<int>Cycle;
	for(int i : Path[u][v]) {
		if(roads.count(devient(i))) {
			Cycle.insert(devient(i));
		}
	}
	for(int i:Cycle)cycle.push_back(i);
	return cycle;
}

void findSol() {
	init();
	initTree();
	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 = findCycle2(u, v); //this line has to be optimized to O(n)
		for(int id : cycle) {
			int old = oldValue;
			roads.insert(i);
			roads.erase(id);
			int nouv = Query(i, id);
			if(nouv > old) {
				merge(ROYAL, i);
				merge(BAD, id);
				fusion(id, i);
				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;
			}
		}
	}
	for(int i = 0; i < nbArcs; i++) if(bad(i)) roads.erase(i); else if(good(i)) roads.insert(i);
}

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