Submission #1054368

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1054368	2024-08-12T09:10:13 Z	ihceker	Race (IOI11_race)	C++14	Compilation error	0 ms	0 KB

race

#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,vector<vector<int>>h,vector<int>l){
	vector<vector<pair<int,int>>>adj(n);
	for(int i=0;i<h.size();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);
}

Compilation message

race.cpp: In function 'int best_path(int, int, std::vector<std::vector<int> >, std::vector<int>)':
race.cpp:15:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 |  for(int i=0;i<h.size();i++){
      |              ~^~~~~~~~~
/usr/bin/ld: /tmp/ccdJNi4n.o: in function `main':
grader.cpp:(.text.startup+0x28): undefined reference to `best_path(int, int, int (*) [2], int*)'
collect2: error: ld returned 1 exit status