| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1049306 |
2024-08-08T16:13:54 Z |
beaconmc |
Race (IOI11_race) |
C++14 |
|
52 ms |
135252 KB |
#include "race.h"
#include <bits/stdc++.h>
typedef long long ll;
#define FOR(i,x,y) for(ll i=x; i<y; i++)
#define FORNEG(i,x,y) for(ll i=x; i>y; i--)
using namespace std;
const ll maxn = 200005;
const ll INF = 1000000000;
basic_string<vector<ll>> edges[maxn];
ll par[maxn];
ll centpar[maxn];
ll depth[maxn];
ll realdepth[maxn];
ll ancc[maxn][20];
bool visited[maxn];
ll sub[maxn];
basic_string<array<ll,2>> idkman;
ll ans = INF;
ll KK;
ll sus[1000005];
ll anc(ll a, ll x){
if (a==0) return 0;
if (x==0) return par[a];
if (ancc[a][x] != -1) return ancc[a][x];
return ancc[a][x] = anc(anc(a,x-1),x-1);
}
ll lca(ll a, ll b){
if (depth[a] < depth[b]) swap(a,b);
FORNEG(i,19,-1) if (depth[anc(a, i)] >= depth[b]) a = anc(a,i);
if (a==b) return a;
FORNEG(i,19,-1) if (anc(a,i) != anc(b,i)) a = anc(a,i), b = anc(b,i);
return par[a];
}
void initdfs(ll a,ll p, ll d, ll dd){
par[a] = p;
depth[a] = d;
realdepth[a] = dd;
for (auto&i : edges[a]){
if (i[0] != p) initdfs(i[0], a, d+1, dd+i[1]);
}
}
ll centroid(ll root, ll a, ll p){
for (auto&i : edges[a]){
if (!visited[i[0]] && i[0] != p && sub[i[0]] > sub[root]/2) return centroid(root, i[0], a);
}
return a;
}
void dfs(ll a, ll p){
sub[a] = 1;
for (auto&i : edges[a]){
if(i[0] != p && !visited[i[0]]) dfs(i[0], a), sub[a] += sub[i[0]];
}
}
void dfs2(ll a, ll p, ll d, ll dd){
for (auto&i : edges[a]){
if (i[0] != p && !visited[i[0]]) dfs2(i[0], a, d+1,dd + i[1]);
}
idkman.push_back({d, dd});
}
void build(ll a, ll p){
dfs(a,p);
ll cent = centroid(a, a, p);
centpar[cent] = p;
visited[cent] = 1;
basic_string<ll> seen;
sus[0] = 0;
for (auto&i : edges[cent]){
if (visited[i[0]]) continue;
idkman.clear();
dfs2(i[0], cent, 1, i[1]);
seen.push_back(0);
sus[0] = 0;
for (auto&k : idkman){
ll req = KK - k[1];
if (0<=req && req <= KK) ans = min(ans, k[0] + sus[req]);
}
for (auto&k : idkman){
seen.push_back(k[1]);
if (0<=k[1] && k[1] <= KK) sus[k[1]] = min(sus[k[1]], k[0]);
}
}
for (auto&k : seen) if (0<=k && k<=KK) sus[k] = INF;
for (auto&i : edges[cent]){
if (!visited[i[0]]) build(i[0], cent);
}
}
basic_string<array<ll,3>> dists[maxn];
int best_path(int N, int K, int H[][2], int L[])
{
KK = K;
FOR(i,0,maxn) par[i] = -1, centpar[i] = -1, par[i] -1, depth[i] = -1, realdepth[i] = -1,visited[i] = 0,dists[i].clear(),edges[i].clear(), sus[i] = INF;
FOR(i,0,maxn)FOR(j,0,20) ancc[i][j] = -1;
FOR(i,0,1000005) sus[i] = INF;
FOR(i,0,N-1){
edges[H[i][0]].push_back({H[i][1], L[i]});
edges[H[i][1]].push_back({H[i][0], L[i]});
}
initdfs(0,-1,0,0);
dfs(0,-1);
build(0,-1);
if (ans >= INF) return -1;
else return ans;
}
Compilation message
race.cpp: In function 'int best_path(int, int, int (*)[2], int*)':
race.cpp:112:56: warning: right operand of comma operator has no effect [-Wunused-value]
112 | FOR(i,0,maxn) par[i] = -1, centpar[i] = -1, par[i] -1, depth[i] = -1, realdepth[i] = -1,visited[i] = 0,dists[i].clear(),edges[i].clear(), sus[i] = INF;
| ~~~~~~~^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
52 ms |
135252 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
52 ms |
135252 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
52 ms |
135252 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
52 ms |
135252 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
