Submission #1196682

#	Time	Username	Problem	Language	Result	Execution time	Memory
1196682		thdh__	Race (IOI11_race)	C++20	0 / 100	3 ms	4928 KiB

race

#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define eb emplace_back
#define pu push
#define ins insert
#define fi first
#define se second
#define all(a) a.begin(),a.end()
#define bruh ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define fu(x,a,b) for (auto x=a;x<=b;x++)
#define fd(x,a,b) for (auto x=a;x>=b;x--)

using namespace std;
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
//mt19937 mt(chrono::steady_clock::now().time_since_epoch().count());

typedef pair<int, int> ii;
const int N = 2e5+5;
const int mod = 1e9+7;
const int inf = 1e18;
using cd = complex<double>;
const long double PI = acos(-1);
int power(int a,int b) {ll x = 1;if (a >= mod) a%=mod; while (b) {if (b & 1) x = x*a % mod;a = a*a % mod;b>>=1;}return x;} 

int n,k, sz[N], mn[N], ans = inf;
vector<ii> adj[N];
bool check[N];

void predfs(int u, int p) 
{	
	sz[u] = 1;
	for (auto i : adj[u]) 
	{
		int v = i.fi, w = i.se;
		if (v == p || check[v]) continue;
		predfs(v,u);
		sz[u] += sz[v];
	}
}

int centroid(int u, int p, int szz) 
{
	for (auto i : adj[u])
	{
		int v = i.fi, w = i.se;
		if (check[v] || v == p) continue;
		if (sz[v] > szz/2) return centroid(v,u,szz);
	}
	return u;
}

vector<ii> a;
int mxdist = 0;

void dfs1(int u, int p, int dist, int len) 
{
	mxdist = max(dist, mxdist);
	if (dist == k) ans = min(ans, len);
	else if (dist < k) ans = min(ans, mn[k-dist] + len);
	a.pb({dist, len});
	for (auto i : adj[u]) 
	{
		int v = i.fi, w = i.se;
		if (v == p || check[v]) continue;
		dfs1(v,u,dist+w,len+1);
	}
}

void dfs(int u) 
{
	predfs(u, 0);
	int ct = centroid(u, 0, sz[u]);
	// cout<<ct<<" ";
	// cout<<endl;
	for (auto i : adj[ct]) 
	{
		int v = i.fi, w = i.se;
		if (check[v]) continue;
		dfs1(v,ct,w,1);
		for (auto j : a) 
		{
			int d = j.fi, l = j.se;
			mn[d] = min(mn[d], l);
		}
	}
	for (int i = 1; i <= mxdist; i++) mn[i] = inf;
	check[ct] = 1;
	for (auto i : adj[ct]) 	
	{
		int v = i.fi, w = i.se;
		if (check[v]) continue;
		dfs(v);
	}
}

// void solve()
// {
// 	cin>>n>>k;
// 	for (int i = 1; i <= k; i++) mn[i] = inf;
// 	for (int i = 1; i < n; i++) 
// 	{
// 		int u,v,l; cin>>u>>v>>l;
// 		adj[u].pb({v,l}); adj[v].pb({u,l});
// 	}
// 	dfs(0);
// 	if (ans == inf) cout<<-1;
// 	else cout<<ans;
// }

int best_path(int N, int K, int H[][2], int L[])
{
	n = N, k = K;
	for (int i = 0; i < n-1; i++) 
	{
		int u = H[i][0], v = H[i][1], l = L[i];
		adj[u].pb({v,l}); adj[v].pb({u,l});
	}
	dfs(0);
	if (ans == inf) return -1;
	else return ans;
}

Compilation message (stderr)

race.cpp:22:17: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   22 | const int inf = 1e18;
      |                 ^~~~

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