# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
67999 |
2018-08-15T17:43:10 Z |
tamtam |
Race (IOI11_race) |
C++14 |
|
3000 ms |
28168 KB |
#include "race.h"
#include <bits/stdc++.h>
#include<unordered_map>
#define F first
#define S second
typedef long long ll;
using namespace std;
int n,k;
int ans=1000000000;
vector<pair<int,int> > v[200010];
bool blocked [200010];
int dep[1000010];
int P[200010];
//unordered_map<int,int> dep;
int Size[200010];
void dfsSize(int nod,int pt){
Size[nod]=1;
P[nod]=pt;
// cout <<"=============== "<<nod<<endl;
for (int i=0;i<v[nod].size();i++){
if (v[nod][i].F==pt||blocked[v[nod][i].F])continue;
dfsSize(v[nod][i].F,nod);
Size[nod]+=Size[v[nod][i].F];
}
}
vector<pair<int,int> > comp;
int dfsAdd (int nod,int pt,int d,int d1){
if (d>k)return 1000000000;
//dep[d]=min(dep[d],d1);
int res=dep[k-d]+d1;
comp.push_back({d,d1});
for (int i=0;i<v[nod].size();i++){
if (v[nod][i].F==pt||blocked[v[nod][i].F])continue;
res=min(res,dfsAdd(v[nod][i].F,nod,d+v[nod][i].S,d1+1));
}
return res;
}
void dfsRem(int nod,int pt,int d){
if (d>k)return;
dep[d]=1000000000;
for (int i=0;i<v[nod].size();i++){
if (v[nod][i].F==pt||blocked[v[nod][i].F])continue;
dfsRem(v[nod][i].F,nod,d+v[nod][i].S);
}
}
int rrr=0;
int Solve (int nod){
rrr++;
if (rrr>n)assert(0);
//cout <<nod<<" -------------\n";
dep[0]=0;
int res=1000000000;
for (int i=0;i<v[nod].size();i++){
if (blocked[v[nod][i].F])continue;
res=min(res,dfsAdd(v[nod][i].F,nod,v[nod][i].S,1));
pair<int,int>qwe;
while (comp.size()>0){
qwe=comp[comp.size()-1];
comp.pop_back();
int d=qwe.F;
int d1=qwe.S;
dep[d]=min(dep[d],d1);
}
//res=min(res,dfsCount(v[nod][i].F,nod,v[nod][i].S,1));
}
dfsRem (nod,-1,0);
return res;
}
int rr;
void Create (int nod0){
rr++;
if (rr>n)assert(0);
//if (vis[nod0]>)return;
//vis[nod0]=1;
//cout <<nod0<<" asdf\n";
dfsSize(nod0,-1);
pair<int,int> cen={Size[nod0],nod0};
//for (int i=0;i<n;i++){
//cout <<Size[i]<<" ";
//}cout <<endl;
int centroid=nod0,mn=1e9;
int nod=nod0,curmx=0;
while (1){
int z=0;
for (int i=0;i<v[nod].size();i++){
if (blocked[v[nod][i].F])continue;
if (v[nod][i].F==P[nod]){
if (curmx<Size[nod0]-Size[nod])z=v[nod][i].F;
curmx=max(curmx,Size[nod0]-Size[nod]);
continue;
}
if (curmx<Size[v[nod][i].F])z=v[nod][i].F;
curmx=max(curmx,Size[v[nod][i].F]);
}
if (curmx<mn){
mn=curmx;
centroid=nod;
nod=z;
curmx=0;
}else break;
}
cen.S=centroid;
//if (blocked[cen.S])return;
//cout <<cen.S<<endl;
blocked[cen.S]=true;
ans=min(Solve(cen.S),ans);
for (int i=0;i<v[cen.S].size();i++){
if (blocked[v[cen.S][i].F])continue;
Create(v[cen.S][i].F);
}
}
int best_path(int N, int K, int H[][2], int L[]){
n=N;k=K;
//if (n<80000||n>100000)return 0;
//if (K<)return 0;
for (int i=0;i<=K;i++){
dep[i]=1000000000;
}
for (int i=0;i<n-1;i++){
int x=H[i][0];
int y=H[i][1];
//cout <<x<<" - "<<y<<endl;
v[x].push_back({y,L[i]});
v[y].push_back({x,L[i]});
}
Create (0);
if (ans==1000000000)return -1;
return ans;
}
Compilation message
race.cpp: In function 'void dfsSize(int, int)':
race.cpp:20:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i=0;i<v[nod].size();i++){
~^~~~~~~~~~~~~~
race.cpp: In function 'int dfsAdd(int, int, int, int)':
race.cpp:33:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i=0;i<v[nod].size();i++){
~^~~~~~~~~~~~~~
race.cpp: In function 'void dfsRem(int, int, int)':
race.cpp:43:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i=0;i<v[nod].size();i++){
~^~~~~~~~~~~~~~
race.cpp: In function 'int Solve(int)':
race.cpp:55:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i=0;i<v[nod].size();i++){
~^~~~~~~~~~~~~~
race.cpp: In function 'void Create(int)':
race.cpp:89:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i=0;i<v[nod].size();i++){
~^~~~~~~~~~~~~~
race.cpp:111:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i=0;i<v[cen.S].size();i++){
~^~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
4988 KB |
Output is correct |
2 |
Correct |
7 ms |
5092 KB |
Output is correct |
3 |
Correct |
6 ms |
5092 KB |
Output is correct |
4 |
Correct |
7 ms |
5128 KB |
Output is correct |
5 |
Correct |
6 ms |
5204 KB |
Output is correct |
6 |
Correct |
6 ms |
5204 KB |
Output is correct |
7 |
Correct |
7 ms |
5280 KB |
Output is correct |
8 |
Correct |
7 ms |
5280 KB |
Output is correct |
9 |
Correct |
8 ms |
5280 KB |
Output is correct |
10 |
Correct |
7 ms |
5280 KB |
Output is correct |
11 |
Correct |
7 ms |
5280 KB |
Output is correct |
12 |
Correct |
8 ms |
5280 KB |
Output is correct |
13 |
Correct |
8 ms |
5280 KB |
Output is correct |
14 |
Correct |
7 ms |
5280 KB |
Output is correct |
15 |
Correct |
7 ms |
5280 KB |
Output is correct |
16 |
Correct |
7 ms |
5280 KB |
Output is correct |
17 |
Correct |
7 ms |
5280 KB |
Output is correct |
18 |
Correct |
7 ms |
5280 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
4988 KB |
Output is correct |
2 |
Correct |
7 ms |
5092 KB |
Output is correct |
3 |
Correct |
6 ms |
5092 KB |
Output is correct |
4 |
Correct |
7 ms |
5128 KB |
Output is correct |
5 |
Correct |
6 ms |
5204 KB |
Output is correct |
6 |
Correct |
6 ms |
5204 KB |
Output is correct |
7 |
Correct |
7 ms |
5280 KB |
Output is correct |
8 |
Correct |
7 ms |
5280 KB |
Output is correct |
9 |
Correct |
8 ms |
5280 KB |
Output is correct |
10 |
Correct |
7 ms |
5280 KB |
Output is correct |
11 |
Correct |
7 ms |
5280 KB |
Output is correct |
12 |
Correct |
8 ms |
5280 KB |
Output is correct |
13 |
Correct |
8 ms |
5280 KB |
Output is correct |
14 |
Correct |
7 ms |
5280 KB |
Output is correct |
15 |
Correct |
7 ms |
5280 KB |
Output is correct |
16 |
Correct |
7 ms |
5280 KB |
Output is correct |
17 |
Correct |
7 ms |
5280 KB |
Output is correct |
18 |
Correct |
7 ms |
5280 KB |
Output is correct |
19 |
Correct |
6 ms |
5280 KB |
Output is correct |
20 |
Correct |
7 ms |
5280 KB |
Output is correct |
21 |
Correct |
7 ms |
5360 KB |
Output is correct |
22 |
Correct |
12 ms |
8940 KB |
Output is correct |
23 |
Correct |
11 ms |
8940 KB |
Output is correct |
24 |
Correct |
10 ms |
8940 KB |
Output is correct |
25 |
Correct |
11 ms |
8940 KB |
Output is correct |
26 |
Correct |
10 ms |
8940 KB |
Output is correct |
27 |
Correct |
10 ms |
8940 KB |
Output is correct |
28 |
Correct |
9 ms |
8940 KB |
Output is correct |
29 |
Correct |
10 ms |
8940 KB |
Output is correct |
30 |
Correct |
10 ms |
8940 KB |
Output is correct |
31 |
Correct |
11 ms |
8940 KB |
Output is correct |
32 |
Correct |
9 ms |
8940 KB |
Output is correct |
33 |
Correct |
12 ms |
8940 KB |
Output is correct |
34 |
Correct |
11 ms |
8940 KB |
Output is correct |
35 |
Correct |
9 ms |
8940 KB |
Output is correct |
36 |
Correct |
9 ms |
9064 KB |
Output is correct |
37 |
Correct |
10 ms |
9064 KB |
Output is correct |
38 |
Correct |
11 ms |
9064 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
4988 KB |
Output is correct |
2 |
Correct |
7 ms |
5092 KB |
Output is correct |
3 |
Correct |
6 ms |
5092 KB |
Output is correct |
4 |
Correct |
7 ms |
5128 KB |
Output is correct |
5 |
Correct |
6 ms |
5204 KB |
Output is correct |
6 |
Correct |
6 ms |
5204 KB |
Output is correct |
7 |
Correct |
7 ms |
5280 KB |
Output is correct |
8 |
Correct |
7 ms |
5280 KB |
Output is correct |
9 |
Correct |
8 ms |
5280 KB |
Output is correct |
10 |
Correct |
7 ms |
5280 KB |
Output is correct |
11 |
Correct |
7 ms |
5280 KB |
Output is correct |
12 |
Correct |
8 ms |
5280 KB |
Output is correct |
13 |
Correct |
8 ms |
5280 KB |
Output is correct |
14 |
Correct |
7 ms |
5280 KB |
Output is correct |
15 |
Correct |
7 ms |
5280 KB |
Output is correct |
16 |
Correct |
7 ms |
5280 KB |
Output is correct |
17 |
Correct |
7 ms |
5280 KB |
Output is correct |
18 |
Correct |
7 ms |
5280 KB |
Output is correct |
19 |
Correct |
206 ms |
11260 KB |
Output is correct |
20 |
Correct |
247 ms |
11264 KB |
Output is correct |
21 |
Correct |
250 ms |
11388 KB |
Output is correct |
22 |
Correct |
259 ms |
11452 KB |
Output is correct |
23 |
Correct |
147 ms |
11452 KB |
Output is correct |
24 |
Correct |
118 ms |
11452 KB |
Output is correct |
25 |
Correct |
250 ms |
13872 KB |
Output is correct |
26 |
Correct |
160 ms |
17276 KB |
Output is correct |
27 |
Correct |
380 ms |
17276 KB |
Output is correct |
28 |
Correct |
551 ms |
28168 KB |
Output is correct |
29 |
Correct |
570 ms |
28168 KB |
Output is correct |
30 |
Correct |
371 ms |
28168 KB |
Output is correct |
31 |
Correct |
373 ms |
28168 KB |
Output is correct |
32 |
Correct |
344 ms |
28168 KB |
Output is correct |
33 |
Correct |
448 ms |
28168 KB |
Output is correct |
34 |
Correct |
424 ms |
28168 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
4988 KB |
Output is correct |
2 |
Correct |
7 ms |
5092 KB |
Output is correct |
3 |
Correct |
6 ms |
5092 KB |
Output is correct |
4 |
Correct |
7 ms |
5128 KB |
Output is correct |
5 |
Correct |
6 ms |
5204 KB |
Output is correct |
6 |
Correct |
6 ms |
5204 KB |
Output is correct |
7 |
Correct |
7 ms |
5280 KB |
Output is correct |
8 |
Correct |
7 ms |
5280 KB |
Output is correct |
9 |
Correct |
8 ms |
5280 KB |
Output is correct |
10 |
Correct |
7 ms |
5280 KB |
Output is correct |
11 |
Correct |
7 ms |
5280 KB |
Output is correct |
12 |
Correct |
8 ms |
5280 KB |
Output is correct |
13 |
Correct |
8 ms |
5280 KB |
Output is correct |
14 |
Correct |
7 ms |
5280 KB |
Output is correct |
15 |
Correct |
7 ms |
5280 KB |
Output is correct |
16 |
Correct |
7 ms |
5280 KB |
Output is correct |
17 |
Correct |
7 ms |
5280 KB |
Output is correct |
18 |
Correct |
7 ms |
5280 KB |
Output is correct |
19 |
Correct |
6 ms |
5280 KB |
Output is correct |
20 |
Correct |
7 ms |
5280 KB |
Output is correct |
21 |
Correct |
7 ms |
5360 KB |
Output is correct |
22 |
Correct |
12 ms |
8940 KB |
Output is correct |
23 |
Correct |
11 ms |
8940 KB |
Output is correct |
24 |
Correct |
10 ms |
8940 KB |
Output is correct |
25 |
Correct |
11 ms |
8940 KB |
Output is correct |
26 |
Correct |
10 ms |
8940 KB |
Output is correct |
27 |
Correct |
10 ms |
8940 KB |
Output is correct |
28 |
Correct |
9 ms |
8940 KB |
Output is correct |
29 |
Correct |
10 ms |
8940 KB |
Output is correct |
30 |
Correct |
10 ms |
8940 KB |
Output is correct |
31 |
Correct |
11 ms |
8940 KB |
Output is correct |
32 |
Correct |
9 ms |
8940 KB |
Output is correct |
33 |
Correct |
12 ms |
8940 KB |
Output is correct |
34 |
Correct |
11 ms |
8940 KB |
Output is correct |
35 |
Correct |
9 ms |
8940 KB |
Output is correct |
36 |
Correct |
9 ms |
9064 KB |
Output is correct |
37 |
Correct |
10 ms |
9064 KB |
Output is correct |
38 |
Correct |
11 ms |
9064 KB |
Output is correct |
39 |
Correct |
206 ms |
11260 KB |
Output is correct |
40 |
Correct |
247 ms |
11264 KB |
Output is correct |
41 |
Correct |
250 ms |
11388 KB |
Output is correct |
42 |
Correct |
259 ms |
11452 KB |
Output is correct |
43 |
Correct |
147 ms |
11452 KB |
Output is correct |
44 |
Correct |
118 ms |
11452 KB |
Output is correct |
45 |
Correct |
250 ms |
13872 KB |
Output is correct |
46 |
Correct |
160 ms |
17276 KB |
Output is correct |
47 |
Correct |
380 ms |
17276 KB |
Output is correct |
48 |
Correct |
551 ms |
28168 KB |
Output is correct |
49 |
Correct |
570 ms |
28168 KB |
Output is correct |
50 |
Correct |
371 ms |
28168 KB |
Output is correct |
51 |
Correct |
373 ms |
28168 KB |
Output is correct |
52 |
Correct |
344 ms |
28168 KB |
Output is correct |
53 |
Correct |
448 ms |
28168 KB |
Output is correct |
54 |
Correct |
424 ms |
28168 KB |
Output is correct |
55 |
Correct |
26 ms |
28168 KB |
Output is correct |
56 |
Correct |
22 ms |
28168 KB |
Output is correct |
57 |
Correct |
117 ms |
28168 KB |
Output is correct |
58 |
Execution timed out |
3053 ms |
28168 KB |
Time limit exceeded |
59 |
Halted |
0 ms |
0 KB |
- |