Submission #787799

#	Time	Username	Problem	Language	Result	Execution time	Memory
787799		allin27x	Race (IOI11_race)	C++17	100 / 100	540 ms	136840 KiB

race

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

int n; int t;
signed ans = 1e7;
unordered_map<int,int> adj[(int)2e5];
int off1[(int)2e5];
int off2[(int)2e5];
unordered_map<int, int> pth[(int)2e5];

void dfs(int i, int p){
	for (auto const &pair1: adj[i]){
		int c = pair1.first; int w = pair1.second;
		if (c==p) continue;
		dfs(c,i);
		off1[c]+=w;
		off2[c]+=1;
		if (pth[i].size() < pth[c].size()){
			swap(pth[i], pth[c]);
			swap(off1[c], off1[i]);
			swap(off2[c], off2[i]);
		}
		for (auto const & pr: pth[c]){
			int s = pr.first; int l = pr.second;
			if (pth[i].count(t-s-off1[c]-off1[i])) ans = min(ans,(signed)(l+pth[i][t-s-off1[c]-off1[i]]+off2[i]+off2[c]));
		}

		for (auto const & pr: pth[c]){
			int s = pr.first; int l = pr.second;
			if (pth[i].count(s-off1[i]+off1[c]))pth[i][s-off1[i]+off1[c]] = min(pth[i][s-off1[i]+off1[c]], l+off2[c]-off2[i]);
			else pth[i][s-off1[i]+off1[c]] = l+off2[c]-off2[i];			
		}
	}
}

signed best_path(signed sz, signed k, signed h[][2], signed l[]){
	n = sz; t=k;
	for (int i=0; i<n-1; i++){
		int a = h[i][0]; int b = h[i][1];
		adj[a][b] = l[i]; adj[b][a] = l[i];
	}
	for (int i=0; i<n; i++) pth[i][0] = 0;
	for (int i=0; i<n; i++) off1[i] = 0;
	for (int i=0; i<n; i++) off2[i] = 0;		
	dfs(0,0);
	if (ans==(int)1e7) return -1;
	return ans;
}

// signed main(){
// 	signed n= 11, k=12;
// 	signed h[n-1][2];
// 	signed 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);
// }

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