Submission #200917

#	Time	Username	Problem	Language	Result	Execution time	Memory
200917		oolimry	Simurgh (IOI17_simurgh)	C++14	100 / 100	260 ms	6136 KiB

simurgh

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

///T is the spanning tree we determine, R is the royal tree

///Phase A: find any spanning tree T of the graph, and determine if each of its edges belong to the royal set in 3N queries
///T is a DFS Tree. For each node, find a back edge that goes up as much as possible. We'll call the cycle formed by the back edge and T a back cycle.

///For any cycle, we can find which edges are royal by fixing the rest of the queried tree, and try to remove each edge from the cycle.
///If the cycle has some edges we know the status of, we need not try to remove all of them, just removing 1 of them as a reference is good enough.
///As all the edges among all cycles (except for the N back edges) belong to T, there are at most 3N queries. (N edges in T + N back edges + N reference edge for each cycle)
///If any edge is not part of any back cycle, then it is a bridge and is surely a royal road

///This spanning tree is useful since we can now query for some forest F, how many edges in F are royal. We can do this just by connecting the forest by adding edges from T into F
///We keep track if we're adding royal edges into F, and later subtract if needed

///Phase B: Determine how many royal edges come out of each node. We can determine a leaf of R. We can binary search all edges of the leaf to find the edge
///Remove the leaf from R, and repeat the process until we get the whole tree. This takes NlogN queries

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; ///finding the furthest back edge
		}
	}
	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){ ///forestEdges are the edges we want to test
	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--; ///acounting for royal roads we add from T
		}
	}
	
	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);
	
	
	///Phase A
	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){ ///Encounter an edge we know the status
				if(reference != -1){ ///Reference has been calculated before (see below code)
					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){ ///First edge we know the status, we set this as the reference
					reference = res;
					if(edgeState[removedEdge] == 1) reference++; ///reference is the value we'd expect after removing an unroyal edge
				}
			}
		}
		
		if(minValue == maxValue){
			for(int e : cycleEdges){
				edgeState[e] = 0; ///a cycle cannot consist of all royal edges
			}
		}
		else{
			for(int i = 0;i < (int) cycleEdges.size();i++){
				if(cycleAnswer[i] == maxValue) edgeState[cycleEdges[i]] = 0;
				else edgeState[cycleEdges[i]] = 1;
			}
		}
		
	}
	
	for(int e : treeEdges){
		if(edgeState[e] == -1) edgeState[e] = 1; ///bridges are royal
	}
	
	
	
	///Phase B
	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 leaf = 0;leaf < n;leaf++){
			if(degree[leaf] != 1) continue; ///finding a node with deegre 1
			
			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;
			
			///Binary search the edge that belongs to the royal tree
			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]);
				}
				
				if(queryForest(query) == 1) high = s;
				else low = s;
			}
			
			///removing the leaf from the royal tree
			int leafEdge = allEdges[high];
			degree[edges[leafEdge].first]--; 
			degree[edges[leafEdge].second]--;
			answer.push_back(leafEdge);
		}
	}
	
	return answer;
}

///Side note: in Phase A, we use queryForest despite not knowing the status of the edges in T.
///This is still ok since the additional edges we add are the same each time

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