Submission #866689

#	Time	Username	Problem	Language	Result	Execution time	Memory
866689		Irate	Race (IOI11_race)	C++14	100 / 100	372 ms	107444 KiB

race

#include<bits/stdc++.h>
#include "race.h"
using namespace std;
const int mxN = 2e5 + 3;
vector<pair<int, int>>G[mxN];
map<long long, int>cnt[mxN]; 
long long length[mxN];
int K, mn = 1e9, depth[mxN];
void dfs(int node, int par){
	cnt[node][length[node]] = depth[node];
	for(pair<int, int>& v : G[node]){
		if(v.first != par){
			depth[v.first] = depth[node] + 1;
			length[v.first] = length[node] + v.second;
			dfs(v.first, node);
			if(cnt[node].size() < cnt[v.first].size())swap(cnt[node], cnt[v.first]);
			for(auto itr = cnt[v.first].begin();itr != cnt[v.first].end();++itr){
				long long num = itr->first;
				int dep = itr->second;
				if(cnt[node].count(K + 2 * length[node] - num)){
					mn = min(mn, dep + cnt[node][K + 2 * length[node] - num] - 2 * depth[node]);
				}
			}
			for(auto itr = cnt[v.first].begin();itr != cnt[v.first].end();++itr){
				if(cnt[node].count(itr->first)){
					cnt[node][itr->first] = min(cnt[node][itr->first], itr->second);
				}
				else{
					cnt[node][itr->first] = itr->second;
				}
			}
		}
	}
}
int best_path(int n, int k, int H[][2], int L[]){
	K = k;
	for(int i = 0;i < n - 1;++i){
		int u = H[i][0], v = H[i][1];
		G[u].push_back({v, L[i]});
		G[v].push_back({u, L[i]});
	}
	dfs(0, 0);
	if(mn == 1e9)return -1;
	return mn;
}
// int main()
// {
// 	ios_base::sync_with_stdio(0);
// 	cin.tie(0);
// 	int n;
// 	cin >> n >> K;
// 	int H[n - 1][2], L[n - 1];
// 	for(int i = 0;i < n - 1;++i){
// 		cin >> H[i][0] >> H[i][1] >> L[i];
// 	}
// 	cout << best_path(n, K, H, L);
// }
/*
11 12
0 1 3
0 2 4 
2 3 5
3 4 4
4 5 6
0 6 3
6 7 2
6 8 5
8 9 6
8 10 7
*/

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