Submission #1055082

#	Time	Username	Problem	Language	Result	Execution time	Memory
1055082		racsosabe	Race (IOI11_race)	C++14	0 / 100	2 ms	2396 KiB

race

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

struct CentroidDecomposition {
	int n;
	int L;
	int T;
	vector<int> a;
	vector<int> h;
	vector<int> in;
	vector<int> sz;
	vector<int> out;
	vector<int> best;
	vector<int> depth;
	vector<bool> removed;
	vector<vector<pair<int, int>>> G;

	CentroidDecomposition(int n, int k) : 
		n(n),
		L(k),
		a(n),
		h(n),
		in(n),
		sz(n),
		out(n),
		best(k + 1, -1),
		depth(n),
		removed(n, false),
		G(n)
	{}

	void add_edge(int u, int v, int w) {
		G[u].emplace_back(v, w);
		G[v].emplace_back(u, w);
	}

	void DFS(int u, int p = -1) {
		sz[u] = 1;
		for(auto e : G[u]) {
			if(e.first == p or removed[e.first]) continue;
			DFS(e.first, u);
			sz[u] += sz[e.first];
		}
	}

	int centroid(int u, int p, int n) {
		for(auto e : G[u]) {
			if(e.first == p or removed[e.first]) continue;
			if(2 * sz[e.first] > n) return centroid(e.first, u, n);
		}
		return u;
	}

	void set_info(int u, int p = -1) {
		a[T] = u;
		in[u] = T++;
		for(auto e : G[u]) {
			int v, w;
			tie(v, w) = e;
			if(v == p or removed[v]) continue;
			depth[v] = depth[u] + 1;
			h[v] = h[u] + w;
			set_info(v, u);
		}
		out[u] = T - 1;
	}

	int compute(int u) {
		h[u] = depth[u] = T = 0;
		set_info(u);
		int res = -1;
		best[0] = 0;
		cout << "Root = " << u << endl;
		for(auto e : G[u]) {
			if(removed[e.first]) continue;
			int v, w;
			tie(v, w) = e;
			cout << "Subtree = " << v << endl;
			for(int i = in[v]; i <= out[v]; i++) {
				int x = a[i];
				if(h[x] > L) continue;
				cout << "Node " << x << " --> " << h[x] << endl;
				cout << "Want = " << L - h[x] << ". Best = " << best[L - h[x]] << endl;
				if(~best[L - h[x]]) {
					cout << "Here" << endl;
					int cand = best[L - h[x]] + depth[x];
					if(res == -1 or cand < res) res = cand;
				}
			}
			cout << endl;
			for(int i = in[v]; i <= out[v]; i++) {
				int x = a[i];
				if(h[x] > L) continue;
				if(best[h[x]] == -1 or best[h[x]] > depth[x]) best[h[x]] = depth[x];
			}
		}
		for(int i = in[u]; i <= out[u]; i++) {
			int x = a[i];
			if(h[x] > L) continue;
			best[h[x]] = -1;
		}
		cout << "Final answer for node " << u << " --> " << res << endl;
		return res;
	}

	int decompose(int rt, int p = -1) {
		DFS(rt, p);
		int c = centroid(rt, p, sz[rt]);
		cout << "Centroid is: " << c << endl;
		int res = compute(c);
		removed[c] = true;
		cout << "New removed table: " << endl;
		for(int i = 0; i < n; i++) {
			cout << removed[i] << " ";
		}
		cout << endl;
		for(auto e : G[c]) {
			if(removed[e.first]) continue;
			int cur = decompose(e.first, c);
			if(cur == -1) continue;
			if(res == -1 or res > cur) res = cur;
		}
		return res;
	}

	int solve() {
		return decompose(0);
	}

};

int best_path(int N, int K, int H[][2], int L[]) {
	CentroidDecomposition Solver(N, K);
	for(int i = 0; i < N - 1; i++) {
		Solver.add_edge(H[i][0], H[i][1], L[i]);
	}
	return Solver.solve();
}

• Subtask 1: 0 / 9
• Subtask 2: 0 / 12
• Subtask 3: 0 / 22
• Subtask 4: 0 / 57