# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
978338 |
2024-05-09T06:29:13 Z |
kwongweng |
Race (IOI11_race) |
C++17 |
|
8 ms |
18268 KB |
#include "race.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef long double ld;
typedef vector<vector<ll>> vll;
#define FOR(i, a, b) for(int i = a; i < b; i++)
#define ROF(i, a, b) for(int i = a; i >= b; i--)
#define pb push_back
#define ms memset
#define fi first
#define se second
const int mxn = 2e5+1;
vii g[mxn]; vi p(mxn);
map<int,int> S[mxn];
int ans;
vector<ll> dist(mxn); // # kilometres from root
vi dist2(mxn); //# highways from root
int k;
//compute distance to root
void dfs1(int u){
for (ii edge : g[u]){
int v = edge.fi; int w = edge.se;
if (p[u]==v) continue;
p[v] = u; dist[v] = dist[u]+w;
dist2[v] = dist2[u]+1; dfs1(v);
}
}
//small to large merging
vi add(mxn); //S[v+add[v]]
void dfs2(int u){
S[u][0] = u;
for (ii edge : g[u]){
int v = edge.fi; int w = edge.se;
if (p[u]==v) continue;
dfs2(v);
add[v]=w;
if (S[u].size()<S[v].size()) {swap(S[u],S[v]); swap(add[u],add[v]);}
for (auto d : S[v]){
int D = d.fi + add[v] + add[u];
if (D > k+2e6) continue;
if (S[u].find(k-D) != S[u].end()){
int v1 = S[u][k-D], v2 = d.se;
//cout<<v1<<" "<<v2<<"\n";
ans = min(ans, dist2[v1] + dist2[v2] - 2*dist2[u]);
}
}
for (auto d : S[v]){
int D = d.fi + add[v] - add[u];
if (D > k+2e6) continue;
if (S[u].find(D) != S[u].end()){
int v1 = S[u][D]; int v2 = d.se;
if (dist2[v2] < dist2[v1]) S[u][D] = v2;
}else{
S[u][D] = d.se;
}
}
}
}
int best_path(int N, int K, int H[][2], int L[])
{
k = K;
ans = N;
FOR(i,0,N-1){
g[H[i][0]].pb({H[i][1],L[i]});
g[H[i][1]].pb({H[i][0],L[i]});
}
dfs1(0); dfs2(0);
if (ans==N) ans = -1;
return ans;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
8 ms |
18268 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
8 ms |
18268 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
8 ms |
18268 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
8 ms |
18268 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |