| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 29442 |
2017-07-19T11:22:20 Z |
Nikefor |
Race (IOI11_race) |
C++ |
|
3000 ms |
12796 KB |
#include "race.h"
#include<bits/stdc++.h>
#define inf 1<<22
using namespace std;
int globalMin = inf;
int target;
int W[1000001];
bool used[200001];
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[adj[n][i].first] 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[(adj[c][i].first)]) 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);
}
}
int centroidfinder(int n) {
int siz = sizer(n,-1);
for(int i=0; i<adj[n].size(); i++) {
if(used[(adj[n][i].first)]) continue;
if(sizer(adj[n][i].first, adj[n][i].second) > siz/2) return centroidfinder(adj[n][i].first);
}
return n;
}
void centroid(int n) {
if( sizer(n, -1)<2 ) return;
// int siz = sizer(n,-1);
int c = centroidfinder(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[(adj[c][i].first)]) 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[c] = true;
for(int i=0; i<kol; i++) if(!used[(adj[c][i].first)] ) 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++) {
~^~~~~~~~~~~~~~~
race.cpp: In function 'int centroidfinder(int)':
race.cpp:44:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0; i<adj[n].size(); i++) {
~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
5112 KB |
Output is correct |
| 2 |
Correct |
7 ms |
5112 KB |
Output is correct |
| 3 |
Correct |
7 ms |
5152 KB |
Output is correct |
| 4 |
Correct |
6 ms |
5300 KB |
Output is correct |
| 5 |
Correct |
6 ms |
5300 KB |
Output is correct |
| 6 |
Correct |
7 ms |
5300 KB |
Output is correct |
| 7 |
Correct |
7 ms |
5300 KB |
Output is correct |
| 8 |
Correct |
6 ms |
5324 KB |
Output is correct |
| 9 |
Correct |
7 ms |
5332 KB |
Output is correct |
| 10 |
Correct |
7 ms |
5332 KB |
Output is correct |
| 11 |
Correct |
7 ms |
5356 KB |
Output is correct |
| 12 |
Correct |
7 ms |
5356 KB |
Output is correct |
| 13 |
Correct |
7 ms |
5356 KB |
Output is correct |
| 14 |
Correct |
6 ms |
5356 KB |
Output is correct |
| 15 |
Correct |
7 ms |
5356 KB |
Output is correct |
| 16 |
Correct |
7 ms |
5356 KB |
Output is correct |
| 17 |
Correct |
7 ms |
5356 KB |
Output is correct |
| 18 |
Correct |
6 ms |
5356 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
5112 KB |
Output is correct |
| 2 |
Correct |
7 ms |
5112 KB |
Output is correct |
| 3 |
Correct |
7 ms |
5152 KB |
Output is correct |
| 4 |
Correct |
6 ms |
5300 KB |
Output is correct |
| 5 |
Correct |
6 ms |
5300 KB |
Output is correct |
| 6 |
Correct |
7 ms |
5300 KB |
Output is correct |
| 7 |
Correct |
7 ms |
5300 KB |
Output is correct |
| 8 |
Correct |
6 ms |
5324 KB |
Output is correct |
| 9 |
Correct |
7 ms |
5332 KB |
Output is correct |
| 10 |
Correct |
7 ms |
5332 KB |
Output is correct |
| 11 |
Correct |
7 ms |
5356 KB |
Output is correct |
| 12 |
Correct |
7 ms |
5356 KB |
Output is correct |
| 13 |
Correct |
7 ms |
5356 KB |
Output is correct |
| 14 |
Correct |
6 ms |
5356 KB |
Output is correct |
| 15 |
Correct |
7 ms |
5356 KB |
Output is correct |
| 16 |
Correct |
7 ms |
5356 KB |
Output is correct |
| 17 |
Correct |
7 ms |
5356 KB |
Output is correct |
| 18 |
Correct |
6 ms |
5356 KB |
Output is correct |
| 19 |
Correct |
6 ms |
5356 KB |
Output is correct |
| 20 |
Correct |
5 ms |
5356 KB |
Output is correct |
| 21 |
Correct |
8 ms |
5356 KB |
Output is correct |
| 22 |
Correct |
2192 ms |
12604 KB |
Output is correct |
| 23 |
Correct |
1755 ms |
12604 KB |
Output is correct |
| 24 |
Correct |
2024 ms |
12604 KB |
Output is correct |
| 25 |
Correct |
1908 ms |
12604 KB |
Output is correct |
| 26 |
Correct |
761 ms |
12604 KB |
Output is correct |
| 27 |
Correct |
1837 ms |
12604 KB |
Output is correct |
| 28 |
Correct |
446 ms |
12604 KB |
Output is correct |
| 29 |
Correct |
726 ms |
12604 KB |
Output is correct |
| 30 |
Correct |
847 ms |
12604 KB |
Output is correct |
| 31 |
Correct |
1469 ms |
12604 KB |
Output is correct |
| 32 |
Correct |
1641 ms |
12604 KB |
Output is correct |
| 33 |
Correct |
1843 ms |
12604 KB |
Output is correct |
| 34 |
Correct |
1487 ms |
12604 KB |
Output is correct |
| 35 |
Correct |
1894 ms |
12604 KB |
Output is correct |
| 36 |
Correct |
2056 ms |
12796 KB |
Output is correct |
| 37 |
Correct |
1673 ms |
12796 KB |
Output is correct |
| 38 |
Correct |
1192 ms |
12796 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
5112 KB |
Output is correct |
| 2 |
Correct |
7 ms |
5112 KB |
Output is correct |
| 3 |
Correct |
7 ms |
5152 KB |
Output is correct |
| 4 |
Correct |
6 ms |
5300 KB |
Output is correct |
| 5 |
Correct |
6 ms |
5300 KB |
Output is correct |
| 6 |
Correct |
7 ms |
5300 KB |
Output is correct |
| 7 |
Correct |
7 ms |
5300 KB |
Output is correct |
| 8 |
Correct |
6 ms |
5324 KB |
Output is correct |
| 9 |
Correct |
7 ms |
5332 KB |
Output is correct |
| 10 |
Correct |
7 ms |
5332 KB |
Output is correct |
| 11 |
Correct |
7 ms |
5356 KB |
Output is correct |
| 12 |
Correct |
7 ms |
5356 KB |
Output is correct |
| 13 |
Correct |
7 ms |
5356 KB |
Output is correct |
| 14 |
Correct |
6 ms |
5356 KB |
Output is correct |
| 15 |
Correct |
7 ms |
5356 KB |
Output is correct |
| 16 |
Correct |
7 ms |
5356 KB |
Output is correct |
| 17 |
Correct |
7 ms |
5356 KB |
Output is correct |
| 18 |
Correct |
6 ms |
5356 KB |
Output is correct |
| 19 |
Correct |
558 ms |
12796 KB |
Output is correct |
| 20 |
Correct |
504 ms |
12796 KB |
Output is correct |
| 21 |
Correct |
518 ms |
12796 KB |
Output is correct |
| 22 |
Correct |
263 ms |
12796 KB |
Output is correct |
| 23 |
Correct |
324 ms |
12796 KB |
Output is correct |
| 24 |
Correct |
124 ms |
12796 KB |
Output is correct |
| 25 |
Execution timed out |
3067 ms |
12796 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 |
5112 KB |
Output is correct |
| 3 |
Correct |
7 ms |
5152 KB |
Output is correct |
| 4 |
Correct |
6 ms |
5300 KB |
Output is correct |
| 5 |
Correct |
6 ms |
5300 KB |
Output is correct |
| 6 |
Correct |
7 ms |
5300 KB |
Output is correct |
| 7 |
Correct |
7 ms |
5300 KB |
Output is correct |
| 8 |
Correct |
6 ms |
5324 KB |
Output is correct |
| 9 |
Correct |
7 ms |
5332 KB |
Output is correct |
| 10 |
Correct |
7 ms |
5332 KB |
Output is correct |
| 11 |
Correct |
7 ms |
5356 KB |
Output is correct |
| 12 |
Correct |
7 ms |
5356 KB |
Output is correct |
| 13 |
Correct |
7 ms |
5356 KB |
Output is correct |
| 14 |
Correct |
6 ms |
5356 KB |
Output is correct |
| 15 |
Correct |
7 ms |
5356 KB |
Output is correct |
| 16 |
Correct |
7 ms |
5356 KB |
Output is correct |
| 17 |
Correct |
7 ms |
5356 KB |
Output is correct |
| 18 |
Correct |
6 ms |
5356 KB |
Output is correct |
| 19 |
Correct |
6 ms |
5356 KB |
Output is correct |
| 20 |
Correct |
5 ms |
5356 KB |
Output is correct |
| 21 |
Correct |
8 ms |
5356 KB |
Output is correct |
| 22 |
Correct |
2192 ms |
12604 KB |
Output is correct |
| 23 |
Correct |
1755 ms |
12604 KB |
Output is correct |
| 24 |
Correct |
2024 ms |
12604 KB |
Output is correct |
| 25 |
Correct |
1908 ms |
12604 KB |
Output is correct |
| 26 |
Correct |
761 ms |
12604 KB |
Output is correct |
| 27 |
Correct |
1837 ms |
12604 KB |
Output is correct |
| 28 |
Correct |
446 ms |
12604 KB |
Output is correct |
| 29 |
Correct |
726 ms |
12604 KB |
Output is correct |
| 30 |
Correct |
847 ms |
12604 KB |
Output is correct |
| 31 |
Correct |
1469 ms |
12604 KB |
Output is correct |
| 32 |
Correct |
1641 ms |
12604 KB |
Output is correct |
| 33 |
Correct |
1843 ms |
12604 KB |
Output is correct |
| 34 |
Correct |
1487 ms |
12604 KB |
Output is correct |
| 35 |
Correct |
1894 ms |
12604 KB |
Output is correct |
| 36 |
Correct |
2056 ms |
12796 KB |
Output is correct |
| 37 |
Correct |
1673 ms |
12796 KB |
Output is correct |
| 38 |
Correct |
1192 ms |
12796 KB |
Output is correct |
| 39 |
Correct |
558 ms |
12796 KB |
Output is correct |
| 40 |
Correct |
504 ms |
12796 KB |
Output is correct |
| 41 |
Correct |
518 ms |
12796 KB |
Output is correct |
| 42 |
Correct |
263 ms |
12796 KB |
Output is correct |
| 43 |
Correct |
324 ms |
12796 KB |
Output is correct |
| 44 |
Correct |
124 ms |
12796 KB |
Output is correct |
| 45 |
Execution timed out |
3067 ms |
12796 KB |
Time limit exceeded |
| 46 |
Halted |
0 ms |
0 KB |
- |
