oj.uz

Submission #1054372

# Submission time Handle Problem Language Result Execution time Memory
1054372 2024-08-12T09:11:12 Z ihceker Race (IOI11_race) C++14
0 / 100
 3000 ms 2396 KB 
#include<bits/stdc++.h>
#include"race.h"
#define ll long long
#define MOD 1000000007
#define all(x) x.begin(),x.end()
#define ff first
#define ss second
#define pb push_back
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);

using namespace std;

int best_path(int n,int k,int h[][2],int l[]){
	vector<vector<pair<int,int>>>adj(n);
	for(int i=0;i<n-1;i++){
		adj[h[i][0]].pb({h[i][1],l[i]});
		adj[h[i][1]].pb({h[i][0],l[i]});
	}
	vector<int>vis(n),sub(n);
	auto dfs=[&](int node,int p,auto&& dfs)->void{
		sub[node]=1;
		for(auto i:adj[node]){
			if(vis[i.ff] || i.ff==p)continue;
			dfs(i.ff,node,dfs);
			sub[node]+=sub[i.ff];
		}
		return;
	};
	vector<int>cnt(k+1,-1);
	auto dfs2=[&](int node,int p,int dep,int len,vector<pair<int,int>>&depths,auto&& dfs2)->void{
		depths.pb({len,dep});
		for(auto i:adj[node]){
			if(vis[i.ff] || i.ff==p)continue;
			dfs2(i.ff,node,dep+1,len+i.ss,depths,dfs2);
		}
		return;
	};
	auto get_centroid=[&](int node)->int{
		bool end=false;
		int p=-1,sz=sub[node];
		while(!end){
			end=true;
			for(auto i:adj[node]){
				if(vis[i.ff] || i.ff==p || sub[i.ff]<=sz/2)continue;
				p=node;
				node=i.ff;
				end=false;
			}
		}
		return node;
	};
	int ans=2e9;
	auto calc=[&](int node,auto&& calc)->void{
		vis[node]=1;
		vector<vector<pair<int,int>>>depths;
		for(auto i:adj[node]){
			if(!vis[i.ff]){
				depths.pb(vector<pair<int,int>>{});
				dfs2(i.ff,node,1,i.ss,depths.back(),dfs2);
			}
		}
		cnt[0]=0;
		for(auto i:depths){
			for(auto j:i){
				if(j.ff>k)continue;
				if(cnt[k-j.ff]!=-1){
					ans=min(ans,j.ss+cnt[k-j.ff]);
				}
			}
			for(auto j:i){
				if(j.ff>k)continue;
				if(cnt[j.ff]==-1)cnt[j.ff]=j.ss;
				else cnt[j.ff]=min(cnt[j.ff],j.ss);
			}
		}
		for(auto i:depths){
			for(auto j:i){
				if(j.ff>k)continue;
				cnt[j.ff]=-1;
			}
		}
		for(auto i:adj[node]){
			if(vis[i.ff])continue;
			dfs(i.ff,node,dfs);
			int v=get_centroid(i.ff);
			calc(v,calc);
		}
	};
	int s=get_centroid(0);
	calc(s,calc);
	return (ans==2e9?-1:ans);
}

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3073 ms 2396 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3073 ms 2396 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3073 ms 2396 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3073 ms 2396 KB Time limit exceeded
2 Halted 0 ms 0 KB -