Submission #339530

#	Time	Username	Problem	Language	Result	Execution time	Memory
339530		penguinhacker	Race (IOI11_race)	C++14	100 / 100	1034 ms	38748 KiB

race

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

#define ll long long
#define ar array

#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
struct my_hash {
    const uint64_t RANDOM = chrono::steady_clock::now().time_since_epoch().count();
    static uint64_t splitmix64(uint64_t x) {
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }
    size_t operator()(uint64_t x) const {
        return splitmix64(x + RANDOM);
    }
};

const int mxN = 200000;
int n, k, ans, sz[mxN];
bool dead[mxN];
vector<pair<int, int>> adj[mxN];

int dfs_sz(int u, int p) {
	sz[u] = 1;
	for (pair<int, int> v : adj[u]) if (v.first != p && !dead[v.first])
		sz[u] += dfs_sz(v.first, u);
	return sz[u];
}

int get_centroid(int u, int p, int tree_sz) {
	for (pair<int, int> v : adj[u]) if (v.first != p && !dead[v.first] && 2 * sz[v.first] > tree_sz)
		return get_centroid(v.first, u, tree_sz);
	return u;
}

gp_hash_table<int, int, my_hash> mp, mp2;
void upd(int wd, int d, gp_hash_table<int, int, my_hash>& m) {
	auto it = m.find(wd);
	if (it == m.end()) {
		m[wd] = d;
	}
	else {
		it->second = min(it->second, d);
	}
}

void dfs(int u, int p, int d, int wd, gp_hash_table<int, int, my_hash>& m) {
	if (wd > k) return;
	if (wd == k) {
		ans = min(ans, d);
		return;
	}
	upd(wd, d, m);
	for (pair<int, int> v : adj[u]) if (v.first != p && !dead[v.first]) {
		dfs(v.first, u, d + 1, wd + v.second, m);
	}
}

void centroid(int u = 0) {
	u = get_centroid(u, -1, dfs_sz(u, -1));
	dfs_sz(u, -1);
	int big = -1;
	for (pair<int, int> v : adj[u]) if (!dead[v.first]) {
		if (big == -1 || sz[v.first] > sz[big]) {
			big = v.first;
		}
	}
	if (big == -1) return;
	for (pair<int, int> v : adj[u]) if (v.first == big) {
		dfs(v.first, u, 1, v.second, mp);
	}
	for (pair<int, int> v : adj[u]) if (!dead[v.first] && v.first != big) {
		dfs(v.first, u, 1, v.second, mp2);
		for (const pair<int, int>& p : mp2) {
			auto it = mp.find(k - p.first);
			if (it != mp.end()) {
				ans = min(ans, p.second + it->second);
			}
		}
		for (const pair<int, int>& p : mp2) {
			upd(p.first, p.second, mp);
		}
		mp2.clear();
	}	
	mp.clear();
	dead[u] = 1;
	for (pair<int, int> v : adj[u]) if (!dead[v.first]) {
		centroid(v.first);
	}
	dead[u] = 0;
}

int best_path(int _n, int _k, int h[][2], int l[]) {
	n = _n, k = _k, ans = INT_MAX;
	for (int i = 0; i < n - 1; ++i) {
		int u = h[i][0], v = h[i][1], w = l[i];
		adj[u].emplace_back(v, w);
		adj[v].emplace_back(u, w);
	}
	centroid();
	if (ans == INT_MAX) ans = -1;
	return ans;
}

/*int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n, k; cin >> n >> k;
	int h[n - 1][2];
	int l[n - 1];
	for (int i = 0; i < n - 1; ++i) {
		cin >> h[i][0] >> h[i][1];
	}
	for (int i = 0; i < n - 1; ++i) {
		cin >> l[i];
	}
	cout << best_path(n, k, h, l);
	return 0;
}
*/

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