# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
970016 |
2024-04-26T06:10:24 Z |
lurhx |
Race (IOI11_race) |
C++17 |
|
3000 ms |
2396 KB |
#include "race.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define mp make_pair
#define f first
#define s second
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);
while(true){
}
if(_ == inf)
_ =-1;
return _;
}
/*
int main() {
cin >> n >> 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++) {
cin >> in[i].f >> in[i].s >> len[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;
cout << _;
}*/
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
3037 ms |
2396 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
3037 ms |
2396 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
3037 ms |
2396 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
3037 ms |
2396 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |