# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
970012 |
2024-04-26T05:56:02 Z |
lurhx |
Race (IOI11_race) |
C++14 |
|
0 ms |
0 KB |
#include "race.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ll long long
#define mp make_pair
#define f first
#define s second
#define ld long double
#pragma GCC optimize("02")
#pragma GCC diagnostic ignored "-Wunused-label"
#pragma GCC diagnostic ignored "-Wunused-variable"
#pragma GCC diagnostic ignored "-Wunused-but-set-variable"
#pragma GCC diagnostic ignored "-Wsign-compare"
const int inf = 1e9;
vector<vector<pair<int,int>>> edges;
vector<bool> centroids;
vector<int> sizes;
int n,k;
int get_size(int node, int parent = -1) {
int res = 1;
for(auto i: edges[node]) {
if(centroids[i.f] || i.f==parent)continue;
res+=get_size(i.f,node);
}
return sizes[node]=res;
}
int get_centroid(int node,int parent = -1) {
for(auto i: edges[node]) {
if(centroids[i.f] || i.f == parent)continue;
if(sizes[i.f]*2>n)
return get_centroid(i.f,node);
}
return node;
}
map<int,int> dis1,dis2;
void dfs(int node,int val,int times,int parent = -1) {
if(dis1.find(val)==dis1.end()) {
dis1[val] = times;
}else {
if(dis2.find(val)==dis2.end())
dis2[val] = times;
else
dis2[val] = min(dis2[val],times);
if(dis2[val]<dis1[val])
swap(dis2[val],dis1[val]);
}
for(auto i: edges[node]) {
if(i.f==parent || centroids[i.f]) continue;
dfs(i.f,val+i.s,times+1,node);
}
}
int solve(int node) {
dis1.clear();
dis2.clear();
//find centroid;
get_size(node);
int centroid = get_centroid(node);
centroids[centroid] = true;
dfs(centroid,0,0);
int ans = inf;
for(auto i: dis1) {
int need = k-i.f;
if(need == i.f) {
if(dis2.find(need)!=dis2.end())
ans = min(ans,i.s+dis2[need]);
}else {
if(dis1.find(need)!=dis1.end())
ans = min(ans,i.s+dis1[need]);
}
}
for(auto i: edges[centroid]) {
if(!centroids[i.f])
ans = min(ans,solve(i.f));
}
return ans;
}
int best_path(int N, int K, int H[][2], int L[]){
n = N;
k = K;
edges.resize(n);
sizes.resize(n);
centroids.resize(n);
pair<int,int> in[n];
int len[n];
for(int i = 0; i<n-1; i++) {
in[i].f = H[i][0]; in[i].s = H[i][1]; len[i] = L[i];
edges[in[i].f].emplace_back(in[i].s,len[i]);
edges[in[i].s].emplace_back(in[i].f,len[i]);
}
auto _ = solve(0);
if(_ == inf)
_ =-1;
return _;
}
Compilation message
/usr/bin/ld: /tmp/ccIfR10W.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