# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
29422 |
2017-07-19T10:30:00 Z |
Nikefor |
Race (IOI11_race) |
C++ |
|
3000 ms |
13472 KB |
#include "race.h"
#include<bits/stdc++.h>
#define inf 1<<22
using namespace std;
int globalMin = inf;
int target;
int W[1000001];
set<int> used;
vector< pair<int,int> > adj[200001];
void centroid(int n);
int sizer(int n, int road) {
int sum = 0;
for(int i=0; i<adj[n].size(); i++) {
if(used.find(adj[n][i].first)==used.end() and (adj[n][i].second!=road)) sum+=sizer(adj[n][i].first, adj[n][i].second);
}
return sum+1;
}
int best_path(int N, int K, int H[][2], int L[])
{
target = K;
for(int i=0; i<N-1; i++) {
int v1 = H[i][0], v2 = H[i][1];
adj[v1].push_back(make_pair(v2, i));
adj[v2].push_back(make_pair(v1, i));
}
for(int i=0; i<N-1; i++) W[i] = L[i];
centroid(0);
return globalMin<inf?globalMin:-1;
}
int A[1000002];
int tmp[1000002];
void DFS(int c, int road, int cost, int edge) {
if(tmp[cost]>edge) tmp[cost] = edge;
if(tmp[cost]+A[target-cost]<globalMin) globalMin = tmp[cost]+A[target-cost];
for(int i =0; i< adj[c].size(); i++) {
if(used.find(adj[c][i].first)!=used.end()) continue;
if(adj[c][i].second!=road and ((cost+W[adj[c][i].second])<=target) ) DFS(adj[c][i].first, adj[c][i].second, cost+W[adj[c][i].second], edge+1);
}
}
void centroid(int n) {
if( sizer(n, -1)<2 ) return;
// int c = centroidibul(int n);
int c = n;
int kol = adj[c].size();
for(int i=1; i<target+1; i++) A[i] = tmp[i] = inf;
A[0] = tmp[0]=0;
for(int i= 0; i<kol; i++) {
if(used.find(adj[c][i].first)!=used.end() ) continue;
for(int j=1; j<=target; j++) tmp[j] = inf;
if(W[adj[c][i].second] <= target )DFS(adj[c][i].first, adj[c][i].second, W[adj[c][i].second], 1);
// for(int j=1; j<target; j++) if((tmp[j]+A[target-j])<globalMin) globalMin = tmp[j]+A[target-j];
for(int j=1; j<target; j++) if(tmp[j]<A[j]) A[j] = tmp[j];
}
used.insert(c);
for(int i=0; i<kol; i++) if(used.find(adj[c][i].first)==used.end() ) centroid(adj[c][i].first);
}
Compilation message
race.cpp: In function 'int sizer(int, int)':
race.cpp:13:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0; i<adj[n].size(); i++) {
~^~~~~~~~~~~~~~
race.cpp: In function 'void DFS(int, int, int, int)':
race.cpp:36:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i =0; i< adj[c].size(); i++) {
~^~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
5112 KB |
Output is correct |
2 |
Correct |
7 ms |
5212 KB |
Output is correct |
3 |
Correct |
7 ms |
5212 KB |
Output is correct |
4 |
Correct |
7 ms |
5212 KB |
Output is correct |
5 |
Correct |
7 ms |
5212 KB |
Output is correct |
6 |
Correct |
9 ms |
5212 KB |
Output is correct |
7 |
Correct |
6 ms |
5232 KB |
Output is correct |
8 |
Correct |
6 ms |
5284 KB |
Output is correct |
9 |
Correct |
6 ms |
5304 KB |
Output is correct |
10 |
Correct |
5 ms |
5304 KB |
Output is correct |
11 |
Correct |
6 ms |
5304 KB |
Output is correct |
12 |
Correct |
5 ms |
5304 KB |
Output is correct |
13 |
Correct |
6 ms |
5304 KB |
Output is correct |
14 |
Correct |
6 ms |
5316 KB |
Output is correct |
15 |
Correct |
6 ms |
5448 KB |
Output is correct |
16 |
Correct |
6 ms |
5448 KB |
Output is correct |
17 |
Correct |
8 ms |
5448 KB |
Output is correct |
18 |
Correct |
7 ms |
5448 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
5112 KB |
Output is correct |
2 |
Correct |
7 ms |
5212 KB |
Output is correct |
3 |
Correct |
7 ms |
5212 KB |
Output is correct |
4 |
Correct |
7 ms |
5212 KB |
Output is correct |
5 |
Correct |
7 ms |
5212 KB |
Output is correct |
6 |
Correct |
9 ms |
5212 KB |
Output is correct |
7 |
Correct |
6 ms |
5232 KB |
Output is correct |
8 |
Correct |
6 ms |
5284 KB |
Output is correct |
9 |
Correct |
6 ms |
5304 KB |
Output is correct |
10 |
Correct |
5 ms |
5304 KB |
Output is correct |
11 |
Correct |
6 ms |
5304 KB |
Output is correct |
12 |
Correct |
5 ms |
5304 KB |
Output is correct |
13 |
Correct |
6 ms |
5304 KB |
Output is correct |
14 |
Correct |
6 ms |
5316 KB |
Output is correct |
15 |
Correct |
6 ms |
5448 KB |
Output is correct |
16 |
Correct |
6 ms |
5448 KB |
Output is correct |
17 |
Correct |
8 ms |
5448 KB |
Output is correct |
18 |
Correct |
7 ms |
5448 KB |
Output is correct |
19 |
Correct |
5 ms |
5448 KB |
Output is correct |
20 |
Correct |
7 ms |
5448 KB |
Output is correct |
21 |
Correct |
11 ms |
5448 KB |
Output is correct |
22 |
Correct |
2572 ms |
12672 KB |
Output is correct |
23 |
Correct |
2197 ms |
12672 KB |
Output is correct |
24 |
Correct |
2268 ms |
12672 KB |
Output is correct |
25 |
Correct |
2083 ms |
12672 KB |
Output is correct |
26 |
Correct |
871 ms |
12672 KB |
Output is correct |
27 |
Correct |
2112 ms |
12672 KB |
Output is correct |
28 |
Correct |
506 ms |
12672 KB |
Output is correct |
29 |
Correct |
792 ms |
12672 KB |
Output is correct |
30 |
Correct |
911 ms |
12672 KB |
Output is correct |
31 |
Correct |
1572 ms |
12672 KB |
Output is correct |
32 |
Correct |
1880 ms |
12672 KB |
Output is correct |
33 |
Correct |
2420 ms |
12672 KB |
Output is correct |
34 |
Correct |
1846 ms |
12672 KB |
Output is correct |
35 |
Correct |
2568 ms |
12672 KB |
Output is correct |
36 |
Correct |
2803 ms |
13040 KB |
Output is correct |
37 |
Correct |
2375 ms |
13040 KB |
Output is correct |
38 |
Correct |
1691 ms |
13040 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
5112 KB |
Output is correct |
2 |
Correct |
7 ms |
5212 KB |
Output is correct |
3 |
Correct |
7 ms |
5212 KB |
Output is correct |
4 |
Correct |
7 ms |
5212 KB |
Output is correct |
5 |
Correct |
7 ms |
5212 KB |
Output is correct |
6 |
Correct |
9 ms |
5212 KB |
Output is correct |
7 |
Correct |
6 ms |
5232 KB |
Output is correct |
8 |
Correct |
6 ms |
5284 KB |
Output is correct |
9 |
Correct |
6 ms |
5304 KB |
Output is correct |
10 |
Correct |
5 ms |
5304 KB |
Output is correct |
11 |
Correct |
6 ms |
5304 KB |
Output is correct |
12 |
Correct |
5 ms |
5304 KB |
Output is correct |
13 |
Correct |
6 ms |
5304 KB |
Output is correct |
14 |
Correct |
6 ms |
5316 KB |
Output is correct |
15 |
Correct |
6 ms |
5448 KB |
Output is correct |
16 |
Correct |
6 ms |
5448 KB |
Output is correct |
17 |
Correct |
8 ms |
5448 KB |
Output is correct |
18 |
Correct |
7 ms |
5448 KB |
Output is correct |
19 |
Correct |
1742 ms |
13472 KB |
Output is correct |
20 |
Correct |
1825 ms |
13472 KB |
Output is correct |
21 |
Correct |
1469 ms |
13472 KB |
Output is correct |
22 |
Correct |
837 ms |
13472 KB |
Output is correct |
23 |
Correct |
723 ms |
13472 KB |
Output is correct |
24 |
Correct |
329 ms |
13472 KB |
Output is correct |
25 |
Execution timed out |
3048 ms |
13472 KB |
Time limit exceeded |
26 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
5112 KB |
Output is correct |
2 |
Correct |
7 ms |
5212 KB |
Output is correct |
3 |
Correct |
7 ms |
5212 KB |
Output is correct |
4 |
Correct |
7 ms |
5212 KB |
Output is correct |
5 |
Correct |
7 ms |
5212 KB |
Output is correct |
6 |
Correct |
9 ms |
5212 KB |
Output is correct |
7 |
Correct |
6 ms |
5232 KB |
Output is correct |
8 |
Correct |
6 ms |
5284 KB |
Output is correct |
9 |
Correct |
6 ms |
5304 KB |
Output is correct |
10 |
Correct |
5 ms |
5304 KB |
Output is correct |
11 |
Correct |
6 ms |
5304 KB |
Output is correct |
12 |
Correct |
5 ms |
5304 KB |
Output is correct |
13 |
Correct |
6 ms |
5304 KB |
Output is correct |
14 |
Correct |
6 ms |
5316 KB |
Output is correct |
15 |
Correct |
6 ms |
5448 KB |
Output is correct |
16 |
Correct |
6 ms |
5448 KB |
Output is correct |
17 |
Correct |
8 ms |
5448 KB |
Output is correct |
18 |
Correct |
7 ms |
5448 KB |
Output is correct |
19 |
Correct |
5 ms |
5448 KB |
Output is correct |
20 |
Correct |
7 ms |
5448 KB |
Output is correct |
21 |
Correct |
11 ms |
5448 KB |
Output is correct |
22 |
Correct |
2572 ms |
12672 KB |
Output is correct |
23 |
Correct |
2197 ms |
12672 KB |
Output is correct |
24 |
Correct |
2268 ms |
12672 KB |
Output is correct |
25 |
Correct |
2083 ms |
12672 KB |
Output is correct |
26 |
Correct |
871 ms |
12672 KB |
Output is correct |
27 |
Correct |
2112 ms |
12672 KB |
Output is correct |
28 |
Correct |
506 ms |
12672 KB |
Output is correct |
29 |
Correct |
792 ms |
12672 KB |
Output is correct |
30 |
Correct |
911 ms |
12672 KB |
Output is correct |
31 |
Correct |
1572 ms |
12672 KB |
Output is correct |
32 |
Correct |
1880 ms |
12672 KB |
Output is correct |
33 |
Correct |
2420 ms |
12672 KB |
Output is correct |
34 |
Correct |
1846 ms |
12672 KB |
Output is correct |
35 |
Correct |
2568 ms |
12672 KB |
Output is correct |
36 |
Correct |
2803 ms |
13040 KB |
Output is correct |
37 |
Correct |
2375 ms |
13040 KB |
Output is correct |
38 |
Correct |
1691 ms |
13040 KB |
Output is correct |
39 |
Correct |
1742 ms |
13472 KB |
Output is correct |
40 |
Correct |
1825 ms |
13472 KB |
Output is correct |
41 |
Correct |
1469 ms |
13472 KB |
Output is correct |
42 |
Correct |
837 ms |
13472 KB |
Output is correct |
43 |
Correct |
723 ms |
13472 KB |
Output is correct |
44 |
Correct |
329 ms |
13472 KB |
Output is correct |
45 |
Execution timed out |
3048 ms |
13472 KB |
Time limit exceeded |
46 |
Halted |
0 ms |
0 KB |
- |