Submission #500892

#	Time	Username	Problem	Language	Result	Execution time	Memory
500892		aymanrs	Race (IOI11_race)	C++14	100 / 100	581 ms	109176 KiB

race

#include <bits/stdc++.h>
using namespace std;
struct node {
	list<pair<node*, int>> l;
	int subtree = 1;
	set<pair<long long, int>>* s = nullptr;
};
int m = 1e9, k;
void dfs(node* n, node* parent, long long sum, int depth){
	int ms = -1;
	node* mc = nullptr;
	for(auto p : n->l){
		if(p.first != parent){
			dfs(p.first, n, sum + p.second, depth + 1);
			n->subtree += p.first->subtree;
			if(p.first->subtree > ms){
				ms = p.first->subtree;
				mc = p.first;
			}
		}
	}
	if(ms == -1){
		n->s = new set<pair<long long, int>>();
	} else {
		n->s = mc->s;
	}
	n->s->insert({sum, depth});
	for(auto p : n->l){
		if(p.first != parent && p.first != mc){
			for(auto f : *p.first->s){
				long long target = k + 2 * sum - f.first;
				auto it = n->s->lower_bound({target, 0});
				if(it != n->s->end() && it->first == target){
					if(f.second + it->second - 2 * depth < m) m = f.second + it->second - 2 * depth;
				}
			}
			for(auto f : *p.first->s){
				n->s->insert(f);
			}
		}
	}
	auto it = n->s->lower_bound({k + sum, 0});
	if(it != n->s->end() && it->first == k + sum){
		if(depth + it->second - 2 * depth < m) m = depth + it->second - 2 * depth;
	}
}
int best_path(int N, int K, int H[][2], int L[]){
	k = K;
	node nodes[N+1];
	int u, v, c;
	for(int i = 0;i < N-1;i++){
		u = H[i][0];
		v = H[i][1];
		c = L[i];
		nodes[u].l.push_back({&nodes[v], c});
		nodes[v].l.push_back({&nodes[u], c});
	}
	dfs(&nodes[1], nullptr, 0, 0);
	map<set<pair<long long, int>>*, bool> del;
	for(int i = 1;i <= N;i++) {
		if(del[nodes[i].s]) continue;
		delete nodes[i].s;
		del[nodes[i].s] = true;
	}
	return m == 1e9 ? -1 : m;
}

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