Submission #538263

#	Time	Username	Problem	Language	Result	Execution time	Memory
538263		myrcella	Race (IOI11_race)	C++17	100 / 100	463 ms	76064 KiB

race

//by szh
#include "race.h"

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

/*

#define MAX_N 500000

static int N, K;
static int H[MAX_N][2];
static int L[MAX_N];
static int solution;

inline 
void my_assert(int e) {if (!e) abort();}

void read_input()
{
  int i;
  my_assert(2==scanf("%d %d",&N,&K));
  for(i=0; i<N-1; i++)
    my_assert(3==scanf("%d %d %d",&H[i][0],&H[i][1],&L[i]));
  my_assert(1==scanf("%d",&solution));
}*/

#define fi first
#define se second
#define pii pair<int,int>
#define pll pair<long long,long long>
#define pb push_back
#define debug(x) cerr<<#x<<"="<<x<<endl
#define pq priority_queue
#define inf 0x3f
#define rep(i,a,b) for (int i=a;i<(b);i++)
#define MP make_pair
#define SZ(x) (int(x.size()))
#define ll long long
#define mod 1000000007
#define ALL(x) x.begin(),x.end()
void inc(int &a,int b) {a=(a+b)%mod;}
void dec(int &a,int b) {a=(a-b+mod)%mod;}
int lowbit(int x) {return x&(-x);}
ll p0w(ll base,ll p) {ll ret=1;while(p>0){if (p%2ll==1ll) ret=ret*base%mod;base=base*base%mod;p/=2ll;}return ret;}

const int maxn = 2e5+10;

vector <pii> edge[maxn];
int ans = mod;
ll len;

map <ll,int> dfs(int u,int fa,int dep,ll depl) {
	map<ll,int> ret;
	for (pii v:edge[u]) {
		if (v.fi==fa) continue;
		map<ll,int> tmp = dfs(v.fi,u,dep+1,depl+(ll)v.se);
		if (SZ(ret)<SZ(tmp)) swap(ret,tmp);
//		debug(SZ(tmp)), debug(SZ(ret)),debug(u);
		for (auto it:tmp) {
			if (ret.find(2*depl+len-it.fi)!=ret.end()) ans = min(ans,ret[2*depl+len-it.fi]+it.se-2*dep);
		}
		for (auto it:tmp) {
			if (ret.find(it.fi)!=ret.end()) ret[it.fi] = min(it.se,ret[it.fi]);
			else ret[it.fi] = it.se;
		}
	}
	ret[depl] = dep;
	if (ret.find(depl+len)!=ret.end()) ans = min (ans,ret[depl+len]-dep);
	return ret;
}

int best_path(int N, int K, int H[][2], int L[]) {
	len = K;
	rep(i,0,N-1) {
		edge[H[i][0]].pb(MP(H[i][1],L[i]));
		edge[H[i][1]].pb({H[i][0],L[i]});
	}
	dfs(0,-1,0,0);
	if (ans == mod) return -1;
	else return ans;
}
/*

int main()
{
  int ans;
  read_input();
  ans = best_path(N,K,H,L);
  if(ans==solution)
    printf("Correct.\n");
  else
    printf("Incorrect. Returned %d, Expected %d.\n",ans,solution);

  return 0;
}
*/

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