Submission #300818

#	Time	Username	Problem	Language	Result	Execution time	Memory
300818		Elephant52	Highway Tolls (IOI18_highway)	C++11	0 / 100	16 ms	7328 KiB

highway

#include "highway.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pair<int, int>> vpi;

#define INF 1000000000
#define F first
#define S second
#define PB push_back
#define MP make_pair
#define rep(i,a,b) for (int i = a; i < b; i++)

typedef struct node {
	int vertex, edge, dist;
	node() {};
	node(int a, int b, int c) : vertex(a), edge(b), dist(c) {};
} node;

vpi adj[90000];
vi tree_adj[90000];
vi edge_dist[90000];
bool seen[90000];
int subtree_sizes[90000];
int depth[90000];

void make_spanning_tree(int cur) {
	seen[cur] = 1;
	for (auto p : adj[cur]) {
		int edge = p.F;
		if (!seen[edge]) {
			make_spanning_tree(edge);
			tree_adj[cur].PB(edge);
			tree_adj[edge].PB(cur);
		}
	}
}

void find_sizes(int cur) {
	seen[cur] = 1;
	subtree_sizes[cur] = 1;
	for (auto edge : tree_adj[cur]) {
		if (!seen[edge]) {
			find_sizes(edge);
			subtree_sizes[cur] += subtree_sizes[edge];
		}
	}
}

int find_centroid(int N) {
	find_sizes(0);
	int centroid = 0, largest_subtree, nxt = 0;
	do {
		centroid = nxt;
		largest_subtree = 0;
		for (auto edge : adj[centroid]) {
			if (subtree_sizes[edge.F] > largest_subtree) {
				largest_subtree = subtree_sizes[N];
				nxt = edge.F;
			}	
		}
	} while(largest_subtree >= N/2+1 && N - subtree_sizes[centroid] >= N/2+1);
	return centroid;
}

void find_pair(int N, vi U, vi V, int A, int B) {
	int S, T, dist, M = V.size();
	
	vi w(M, 0); //query edge list
	
	rep(i,0,M) {
		adj[U[i]].emplace_back(V[i], i);
		adj[V[i]].emplace_back(U[i], i);
	}
	return;
	make_spanning_tree(0);
	memset(seen, 0, sizeof(seen));
	
	queue<pii> bfs;
	bfs.push(MP(find_centroid(N), 1));
	
	int tree_height = 0;
	
	while (!bfs.empty()) {
		pii cur = bfs.front(); bfs.pop(); //vertex, distance
		depth[cur.F] = cur.S;
		tree_height = max(tree_height, cur.S);
		seen[cur.F] = 1;
		
		for (auto edge : adj[cur.F]) {
			edge_dist[cur.S].PB(edge.S);
			if (!seen[edge.F]) bfs.push(MP(edge.F, cur.S));	
		}
	}
	
	assert(A > 0);
	dist = ask(w)/A;
	
	int low = 1, high = tree_height;
	
	while (low < high) {
		int mid = (low + high)/2;
		
		for (int i = tree_height-1; i >= mid; i--) {
			for (auto edge : edge_dist[i]) w[edge] = 1;
		}
		
		int res = ask(w);
		if (res > dist*A) low = mid+1;	
		else high = mid;
		
		memset(&w[0], 0, sizeof(w[0])*M);
	}
	
	int lower_point = low-1; //depth of lower point
	
	low = 0, high = edge_dist[lower_point].size();
	
	while (low < high) {
		int mid = (low + high)/2;
		
		for (int i = 0; i <= mid; i++) w[edge_dist[lower_point][i]] = 1;
		
		int res = ask(w);
		if (res > dist*A) high = mid;	
		else low = mid+1;
		
		memset(&w[0], 0, sizeof(w[0])*M);
	}
	
	S = min(U[edge_dist[lower_point][low]], V[edge_dist[lower_point][low]]);
	if (depth[U[edge_dist[lower_point][low]]] > depth[V[edge_dist[lower_point][low]]]) S = U[edge_dist[lower_point][low]];
	else S = V[edge_dist[lower_point][low]];
	
	queue<node> bfs2;
	
	bfs2.push(node(S, 0, 0));
	
	memset(seen, 0, sizeof(seen));
	while (!bfs2.empty()) {
		auto cur = bfs2.front(); bfs2.pop();
		seen[cur.vertex] = 1;
		if (dist == cur.dist) {
			w[cur.edge] = 1;
			int res = ask(w);
			if (res > dist*A) {
				T = cur.vertex;
				break;
			}
			w[cur.edge] = 0;
		}
		for (auto edge : adj[cur.vertex]) {
			if (!seen[edge.F]) {
				bfs2.push(node(edge.F, edge.S, cur.dist+1));
			}
		}
	}
	
	answer(S, T);
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 7
• Subtask 3: 0 / 6
• Subtask 4: 0 / 33
• Subtask 5: 0 / 18
• Subtask 6: 0 / 31