Submission #200915

#	Time	Username	Problem	Language	Result	Execution time	Memory
200915		oolimry	Simurgh (IOI17_simurgh)	C++14	100 / 100	237 ms	7036 KiB

simurgh

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

typedef pair<int,int> ii;

int n, m;
vector<int> answer;
 
vector<int> adj[505];
int edgeNo[505][505];
int edgeState[250000]; ///-1: unknown, 0: unroyal. 1: royal
ii edges[250000]; ///
int depth[505];
int parent[505];
int back[505];
int degree[505];
vector<ii> backCycles;
vector<int> treeEdges;

void dfs(int u){
	int largestBack = u;
	for(int v : adj[u]){
		if(depth[v] == 0){
			depth[v] = depth[u] + 1;
			parent[v] = u;
			treeEdges.push_back(edgeNo[u][v]);
			dfs(v);
		}
		else if(v != parent[u]){
			if(depth[largestBack] > depth[v]) largestBack = v;
		}
	}
	backCycles.push_back(ii(u, largestBack));
}

struct UFDS{
	int p[505];
	
	void reset(){
		for(int i = 0;i < n;i++) p[i] = i;
	}
	
	int findSet(int u){
		if(u == p[u]) return u;
		else{
			p[u] = findSet(p[u]);
			return p[u];
		}
	}
	
	bool unionSet(int u, int v){
		u = findSet(u); v = findSet(v);
		if(u == v) return false;
		p[u] = v;
		return true;
	}
} uf;

int queryForest(vector<int> forestEdges){
	uf.reset();
	int res = 0;
	
	vector<int> query;
	
	for(int e : forestEdges){
		uf.unionSet(edges[e].first, edges[e].second);
		query.push_back(e);
	}
	
	for(int e : treeEdges){
		if(uf.unionSet(edges[e].first, edges[e].second)){
			query.push_back(e);
			if(edgeState[e] == 1) res--;
		}
	}
	
	res += count_common_roads(query);
	return res;
}

vector<int> find_roads(int N, vector<int> P, vector<int> Q) {
	n = N; m = P.size();
	
	for(int i = 0;i < n;i++) for(int j = 0;j < n;j++) edgeNo[i][j] = -1;
	fill(edgeState,edgeState+m,-1);
	
	for(int i = 0;i < m;i++){
		edgeNo[P[i]][Q[i]] = i; 
		edgeNo[Q[i]][P[i]] = i;
		edges[i] = ii(P[i],Q[i]);
		adj[P[i]].push_back(Q[i]);
		adj[Q[i]].push_back(P[i]);
	}

	depth[0] = 1;
	dfs(0);
	
	
	
	for(ii C : backCycles){
		vector<int> cycleEdges;
		int bottom = C.first, top = C.second;
		if(bottom == top) continue;
		
		cycleEdges.push_back(edgeNo[bottom][top]);
		while(bottom != top){
			int up = parent[bottom];
			cycleEdges.push_back(edgeNo[up][bottom]);
			bottom = up;
		}
		
		vector<int> cycleAnswer;
		int maxValue = 0; int minValue = 600;
		int reference = -1; ///value taken if we know we're excluding an unroyal edge
		
		for(int removedEdge : cycleEdges){
			if(edgeState[removedEdge] != -1){
				if(reference != -1){
					int res = reference;
					if(edgeState[removedEdge] == 1) res--;
					maxValue = max(res, maxValue);
					minValue = min(res, minValue);
					cycleAnswer.push_back(res);
					continue;
				}
			}
			
			vector<int> query;
			for(int e : cycleEdges){
				if(e != removedEdge) query.push_back(e);
			}
			int res = queryForest(query);
			cycleAnswer.push_back(res);
			maxValue = max(res, maxValue);
			minValue = min(res, minValue);
			
			if(edgeState[removedEdge] != -1){
				if(reference == -1){
					reference = res;
					if(edgeState[removedEdge] == 1) reference++;
				}
			}
		}
		
		if(minValue == maxValue){
			for(int e : cycleEdges){
				edgeState[e] = 0;
				//cout << e << " " << edgeState[e] << "D\n";
			}
		}
		else{
			for(int i = 0;i < (int) cycleEdges.size();i++){
				if(cycleAnswer[i] == maxValue) edgeState[cycleEdges[i]] = 0;
				else edgeState[cycleEdges[i]] = 1;
				//cout << cycleEdges[i] << " " << edgeState[cycleEdges[i]] << "D\n";
			}
		}
		
	}
	
	for(int e : treeEdges){
		if(edgeState[e] == -1) edgeState[e] = 1;
		//cout << e << " " << edgeState[e] << "\n";
	}
	
	for(int i = 0;i < n;i++){
		vector<int> query;
		for(int j = 0;j < n;j++){
			if(edgeNo[i][j] != -1){
				query.push_back(edgeNo[i][j]);
			}
		}
		degree[i] = queryForest(query);
	}
	
	
	while((int) answer.size() < n - 1){
		
		for(int i = 0;i < n;i++){
			//cout << degree[i] << " ";
		}
		//cout << endl;
		for(int leaf = 0;leaf < n;leaf++){
			if(degree[leaf] != 1) continue;
			
			//cout << leaf << " "<< endl;
			vector<int> allEdges;
			for(int j = 0;j < n;j++){
				if(edgeNo[leaf][j] != -1 && degree[j] != 0){
					allEdges.push_back(edgeNo[leaf][j]);
				}
			}
			
			int low = -1; int high = allEdges.size() - 1;
			
			//for(int e : allEdges){
			//	cout << edges[e].first << " " << edges[e].second << "E\n";
			//}
			while(true){
				if(low == high - 1) break;
				int s = (low + high) / 2;
				
				vector<int> query;
				for(int i = 0;i <= s;i++){
					query.push_back(allEdges[i]);
				}
				
				//cout << s << " " << queryForest(query) << endl;
				if(queryForest(query) == 1) high = s;
				else low = s;
			}
			
			int leafEdge = allEdges[high];
			degree[edges[leafEdge].first]--; 
			degree[edges[leafEdge].second]--;
			answer.push_back(leafEdge);
			
			//break;
		}
		//break;
	}
	
	return answer;
}

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