# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
33991 |
2017-11-06T01:19:06 Z |
TAMREF |
Race (IOI11_race) |
C++11 |
|
7 ms |
5452 KB |
#include "race.h"
#include <bits/stdc++.h>
#define va first
#define vb second
using namespace std;
typedef long long ll;
typedef pair<int,ll> pil;
const int mx = 2e5+5;
const int mk = 1e6+1;
const int inf = 5e5;
vector<pil> G[mx];
unordered_set<int> depv;
int cnt[mx], par[mx], dep[mx];
int chk[mk], nowchk[mk];
int K_g, N_g, ans=5e5;
bool del[mx];
void setcnt(int r){
cnt[r] = 1;
for(pil &p : G[r]){
if(del[p.va] || p.va == par[r]) continue;
par[p.va] = r;
setcnt(p.va);
cnt[r] += cnt[p.va];
}
}
int centroid(int now, int num){
for(pil &p : G[now]){
if(del[p.va] || p.va == par[now]) continue;
if(cnt[p.va]>num/2) return centroid(p.va,num);
}
return now;
}
void dfs(int now, ll sum){
if(sum <= K_g){
nowchk[sum] = min(nowchk[sum], dep[now]);
//printf("now = %d, sum = %lld, chk[%lld]=%d, nowchk[%lld]=%d\n",now,sum,K_g-sum,chk[K_g-sum],sum,nowchk[sum]);
depv.insert(sum);
ans = min(ans, dep[now] + chk[K_g-sum]);
}
for(pil &p : G[now]){
if(del[p.va] || p.va == par[now]) continue;
par[p.va] = now;
dep[p.va] = dep[now] + 1;
dfs(p.va, sum + p.vb);
}
}
void dnc(int r){
setcnt(r);
int cen = centroid(r,cnt[r]);
//printf("----------centroid is %d----------\n",cen);
dep[cen] = 0;
fill(chk,chk+K_g+1,inf);
for(pil &p : G[cen]){
if(del[p.va]) continue;
dep[p.va] = 1;
par[p.va] = cen;
for(int u : depv) nowchk[u] = inf;
depv.clear();
dfs(p.va,p.vb);
for(int u : depv){
//printf("%d in check\n",u);
chk[u] = min(chk[u],nowchk[u]);
}
}
//puts("----------------------------");
del[cen] = true;
for(pil &p : G[cen]){
if(del[p.va]) continue;
dnc(p.va);
}
}
int best_path(int N, int K, int H[][2], int L[])
{
N_g = N, K_g = K;
for(int i=0;i<N-1;i++){
G[H[i][0]].emplace_back(H[i][1],L[i]);
G[H[i][1]].emplace_back(H[i][0],L[i]);
}
fill(nowchk,nowchk+K+1,inf);
dnc(0);
return ans==inf?-1:ans;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
4984 KB |
Output is correct |
2 |
Correct |
7 ms |
5092 KB |
Output is correct |
3 |
Correct |
6 ms |
5256 KB |
Output is correct |
4 |
Correct |
6 ms |
5256 KB |
Output is correct |
5 |
Correct |
7 ms |
5256 KB |
Output is correct |
6 |
Correct |
7 ms |
5384 KB |
Output is correct |
7 |
Correct |
6 ms |
5384 KB |
Output is correct |
8 |
Incorrect |
7 ms |
5452 KB |
Output isn't correct |
9 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
4984 KB |
Output is correct |
2 |
Correct |
7 ms |
5092 KB |
Output is correct |
3 |
Correct |
6 ms |
5256 KB |
Output is correct |
4 |
Correct |
6 ms |
5256 KB |
Output is correct |
5 |
Correct |
7 ms |
5256 KB |
Output is correct |
6 |
Correct |
7 ms |
5384 KB |
Output is correct |
7 |
Correct |
6 ms |
5384 KB |
Output is correct |
8 |
Incorrect |
7 ms |
5452 KB |
Output isn't correct |
9 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
4984 KB |
Output is correct |
2 |
Correct |
7 ms |
5092 KB |
Output is correct |
3 |
Correct |
6 ms |
5256 KB |
Output is correct |
4 |
Correct |
6 ms |
5256 KB |
Output is correct |
5 |
Correct |
7 ms |
5256 KB |
Output is correct |
6 |
Correct |
7 ms |
5384 KB |
Output is correct |
7 |
Correct |
6 ms |
5384 KB |
Output is correct |
8 |
Incorrect |
7 ms |
5452 KB |
Output isn't correct |
9 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
4984 KB |
Output is correct |
2 |
Correct |
7 ms |
5092 KB |
Output is correct |
3 |
Correct |
6 ms |
5256 KB |
Output is correct |
4 |
Correct |
6 ms |
5256 KB |
Output is correct |
5 |
Correct |
7 ms |
5256 KB |
Output is correct |
6 |
Correct |
7 ms |
5384 KB |
Output is correct |
7 |
Correct |
6 ms |
5384 KB |
Output is correct |
8 |
Incorrect |
7 ms |
5452 KB |
Output isn't correct |
9 |
Halted |
0 ms |
0 KB |
- |