| # |
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 |
- |
