Submission #769915

#	Time	Username	Problem	Language	Result	Execution time	Memory
769915		ByeWorld	Race (IOI11_race)	C++14	100 / 100	352 ms	98828 KiB

race

#include <bits/stdc++.h>
#include "race.h"
#define fi first
#define se second
#define pb push_back
#define ll long long
using namespace std;
typedef pair<ll,ll> pii;
typedef pair<ll, pii> ipii;
const ll MAXN = 2e5+10;
const ll INF = 2e18;
const ll MOD = 1e9+7;

ll n, k;
vector <pii> adj[MAXN];
ll sub[MAXN], big[MAXN], dep[MAXN], off[MAXN];
ll ans = INF;
map <ll, ll> *m[MAXN];

void dfs(ll nw, ll par){
	sub[nw] = 1; dep[nw] = dep[par]+1;
	big[nw] = n+1;
	for(auto ed : adj[nw]){
		ll nx = ed.fi;
		if(nx == par) continue;
		dfs(nx, nw);
		if(sub[nx] > sub[big[nw]]) big[nw] = nx;
		sub[nw] += sub[nx];
	}
}
void upd(ll nw, ll len, ll depth){
	if((*m[nw]).find(len) == (*m[nw]).end()) (*m[nw])[len] = depth;
	else (*m[nw])[len] = min((*m[nw])[len], depth);
}
void dsu(ll nw, ll par){
	if(adj[nw].size() == 1 && par != 0){ //leaf
		m[nw] = new map<ll,ll>;
		upd(nw, 0, dep[nw]);
		return;
	}
	for(auto ed : adj[nw]){
		ll nx = ed.fi; ll wei = ed.se;
		if(nx == par) continue;
		dsu(nx, nw); //dfs
		off[nx] += wei; //nambah edge
	}
	m[nw] = m[big[nw]]; off[nw] = off[big[nw]]; //offset + map sama
	upd(nw, -off[nw], dep[nw]);

	for(auto ed : adj[nw]){
		ll nx = ed.fi; ll wei = ed.se;
		if(nx == par || nx == big[nw]) continue;

		// cek inside
		for(auto in : (*m[nx])){
			ll len = in.fi; ll depth = in.se;
			len += off[nx]; //keluar, nambahin

			if(len > k || (*m[nw]).find(k-len-off[nw]) == (*m[nw]).end() ) continue; //gk ad
			ans = min(ans, (*m[nw])[k-len-off[nw]] + depth - 2*dep[nw]);
			//cek dalem, kurangin
		}
		// merge (*m[nx])
		for(auto in : (*m[nx])){
			ll len = in.fi; ll depth = in.se;
			len += off[nx];
			if( (*m[nw]).find(len-off[nw]) == (*m[nw]).end() ) (*m[nw])[len-off[nw]] = depth;
			else (*m[nw])[len-off[nw]] = min((*m[nw])[len-off[nw]], depth);
		}
	}
	// cout << nw << ' ' << off[nw] << "off\n";
	// for(auto in : (*m[nw])){
	// 	cout << in.fi << ' '<< in.se << '\n';
	// }
	//cek dalem
	if( (*m[nw]).find(k-off[nw]) != (*m[nw]).end() )
		ans = min(ans, (*m[nw])[k-off[nw]] - dep[nw]);
}

int best_path(int N, int K, int H[][2], int L[]){
	n = N; k = K;
	for(ll i=0; i<n-1; i++){
		adj[H[i][0]+1].pb({H[i][1]+1, L[i]});
		adj[H[i][1]+1].pb({H[i][0]+1, L[i]});
	}
	// 1-n
	dfs(1, 0);
	dsu(1, 0);
	return (ans==INF ? -1 : ans);
}

Compilation message (stderr)

race.cpp: In function 'void dsu(long long int, long long int)':
race.cpp:51:21: warning: unused variable 'wei' [-Wunused-variable]
   51 |   ll nx = ed.fi; ll wei = ed.se;
      |                     ^~~

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