Submission #431452

#	Time	Username	Problem	Language	Result	Execution time	Memory
431452		Bill_00	Race (IOI11_race)	C++14	43 / 100	858 ms	127584 KiB

race

#include "race.h"
#include <bits/stdc++.h>
#define ff first
#define ss second
using namespace std;
vector<pair<int,int> >adj[200000];
long long desired;
long long ans=1e9;
struct dp{
	long long val1;
	unordered_map<long long,pair<long long,bool> >um;
	long long val;
	vector<long long>dp;
};
dp tree[200000];
int sz[200000];
void dfs(int node,int par=-1){
	sz[node]=1;
	for(pair<int,int>child:adj[node]){
		if(child.first!=par){
			dfs(child.first,node);
			sz[node]+=sz[child.first];
		}
	}
}
void solve(int node,int par=-1){
	int dis=0;
	pair<int,int>temp,bigchild={0,-1};
	for(pair<int,int>child:adj[node]){
		if(child.ff==par) continue;
		temp={sz[child.ff],child.ff};
		if(temp>bigchild){
			dis=child.ss;
			bigchild=temp;
		}
	}
	if(bigchild.ss!=-1){
		solve(bigchild.ss,node);
		swap(tree[node],tree[bigchild.ss]);
	}
	tree[node].dp.push_back(-dis-tree[node].val);
	tree[node].val+=dis;
	tree[node].val1++;
	tree[node].um[-tree[node].val].first=-tree[node].val1;
	tree[node].um[-tree[node].val].second=1;
	if(tree[node].um[desired-tree[node].val].ss==1){
		ans=min(ans,tree[node].um[desired-tree[node].val].first+tree[node].val1);
	}
	for(pair<int,int>child:adj[node]){
		if(child.ff==par) continue;
		if(child.ff!=bigchild.ss){
			long long dist=child.second;
			solve(child.ff,node);
			for(int i=0;i<tree[child.ff].dp.size();i++){
				long long actual=tree[child.ff].dp[i]+tree[child.ff].val;
				long long dis1=tree[child.ff].um[tree[child.ff].dp[i]].first+tree[child.ff].val1;
				bool flag=tree[node].um[desired-actual-dist-tree[node].val].second;
				long long dis2=tree[node].um[desired-actual-dist-tree[node].val].first+tree[node].val1;
				if(flag==1){
					ans=min(ans,dis1+dis2+1);
				}
				actual+=dist;
				actual-=tree[node].val;
				if(tree[node].um[actual].ss==1){
					tree[node].um[actual].ff=min(tree[node].um[actual].ff,dis1+1-tree[node].val1);
				}
				else{
					tree[node].dp.push_back(actual);
					tree[node].um[actual].ff=dis1+1-tree[node].val1;
					tree[node].um[actual].ss=1;
				}
			}
		}
	}
	// cout << tree[node].val << ' ' << node << '\n';
	// for(int i=0;i<tree[node].dp.size();i++){
	// 	cout << tree[node].dp[i] << ' ';
	// }
	// cout << '\n';
}
int best_path(int N, int K, int H[][2], int L[])
{	
	desired=K;
	for(int i=0;i<(N-1);i++){
		adj[H[i][0]].push_back({H[i][1],L[i]});
		adj[H[i][1]].push_back({H[i][0],L[i]});
	}
	dfs(0);
	solve(0);
	int answer=ans;
	return (1000000000==answer?-1:answer);
}

Compilation message (stderr)

race.cpp: In function 'void solve(int, int)':
race.cpp:54:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |    for(int i=0;i<tree[child.ff].dp.size();i++){
      |                ~^~~~~~~~~~~~~~~~~~~~~~~~~

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