Submission #155828

#	Time	Username	Problem	Language	Result	Execution time	Memory
155828		m1sch3f	Race (IOI11_race)	C++17	100 / 100	1279 ms	60488 KiB

race

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

// types - only for stuff used a lot 
using ll = long long;
#define vv vector
#define Pp pair

// IO
#define get(x) scanf("%d",&x)
#define getl(x) scanf("%lld",&x);

// Operations
#define pb push_back
#define pob pop_back
#define sz(a) int(a.size()) 
#define re(a,b) a=max(a,b) // relax
#define ri(a,b) a=min(a,b) // relaxi

// Debugging

#ifndef LOCAL
#define cerr if (0) cerr
#else
#define cerr cout
#endif

#define print(arr,n) {for (int _ = 0; _ < n; _++) cerr<<arr[_]<<" "; cerr << endl; }
#define printv(vec)  {for (int _ : vec) cerr<<_<<" "; cerr<<endl;}

const int mod = 1e9+7, oo = 1e9;
const ll loo = 1e18;

// Functions 
ll modpow(ll a, ll b) {
	ll ans = 1; // faster modpow than recursive
	for (; b; b/=2,a=a*a%mod)
		if (b&1) ans = (ans*a)%mod;
	return ans;
}
ll gcd(ll a, ll b) {
	while (a) b%=a,swap(a,b);
	return b;
}
#define bitcount __builtin_popcountll
#define f(i,a,b) for (int i = a; i < b; i++)
#define fr(i,a,b) for (int i = b-1; i >= a; i--)


/* 

   ALRIGHT HACKERS, THIS IS WHERE THE ACTUAL CODE BEGINS

 */

const bool DEBUG = 1;

using vi = vector<int>;

const int N = 200000;
map<int,int> freq;
int K, lift = 0, liftnum = 0;
int ans = oo;
vi adj[N];
int a[N],b[N],c[N];
int sz[N];

int query(int L) {
	L -= lift;
	return freq.count(L)?freq[L]+liftnum:oo;
}

void update(int L, int v) {
	L -= lift;
	if (!freq.count(L)) freq[L] = oo;
	ri(freq[L],v-liftnum);
}

int dfs_subsz(int v, int p) {
	sz[v] = 1;
	for (int e : adj[v]) {
		int w = a[e]^b[e]^v;
		if (w != p)
			sz[v] += dfs_subsz(w,v);
	}
	return sz[v];
}

void explore(int v, int p, int d, int dd) {
	ri(ans,dd+query(K-d));
	for (int e : adj[v]) {
		int w = a[e]^b[e]^v;
		if (w != p) explore(w,v,d+c[e],dd+1);
	}	
}

void add(int v, int p, int d, int dd) {
	update(d,dd);
	for (int e : adj[v]) {
		int w = a[e]^b[e]^v;
		if (w != p) add(w,v,d+c[e],dd+1);
	}	
}

void dfs_solve(int v, int p, bool keep) {
	int bigChild = -1, bigSz = -1, bigc = -1;
	for (int e : adj[v]) {
		int w = a[e]^b[e]^v;
		if (w != p && sz[w] > bigSz)
			bigSz = sz[w], bigChild = w, bigc = c[e];
	}
	for (int e : adj[v]) {
		int w = a[e]^b[e]^v;
		if (w != p && w != bigChild)
			dfs_solve(w,v,0);
	}
	if (bigChild != -1) dfs_solve(bigChild,v,1), lift += bigc, liftnum++;
	update(0,0);
	ri(ans,query(K));
	for (int e : adj[v]) {
		int w = a[e]^b[e]^v;
		if (w != p && w != bigChild) {
			explore(w,v,c[e],1);
			add(w,v,c[e],1);
		}
	}
	if (!keep)
		freq = map<int,int>(), lift = liftnum = 0;
}

int best_path(int n, int k, int h[][2], int l[]) {
	K = k;
	f(i,0,n-1) {
		a[i] = h[i][0], b[i] = h[i][1], c[i] = l[i];
		adj[a[i]].pb(i); adj[b[i]].pb(i);
	}
	dfs_subsz(0,-1);
	dfs_solve(0,-1,0);
	return ans==oo?-1:ans;
}

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