# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
990838 |
2024-05-31T13:35:07 Z |
vjudge |
Race (IOI11_race) |
C++14 |
|
269 ms |
40368 KB |
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <vector>
#include <utility>
#include <queue>
using namespace std;
typedef pair<int,int> pi;
vector<pi> graph[200005];
int ret = 1e9;
int size[200005], maxtree[200005];
int kill[200005];
int k;
vector<int> new_vis;
int dfs(int p, int pa){
if(kill[p]) return 0;
new_vis.push_back(p);
int cs = 1;
int maxv = 0;
for (int i=0; i<graph[p].size(); i++) {
if(graph[p][i].second == pa) continue;
int t = dfs(graph[p][i].second,p);
maxv = max(t,maxv);
cs += t;
}
maxtree[p] = maxv;
return size[p] = cs;
}
int get_mid(int p){
for (int i=0; i<new_vis.size(); i++) {
size[new_vis[i]] = 0;
maxtree[new_vis[i]] = 0;
}
new_vis.clear();
int full = dfs(p,-1);
int mid_pos = 0, mid_res =1e9;
for (int i=0; i<new_vis.size(); i++) {
maxtree[new_vis[i]] = max(maxtree[new_vis[i]],full - size[new_vis[i]]);
if(mid_res > maxtree[new_vis[i]]){
mid_pos = new_vis[i];
mid_res = maxtree[mid_pos];
}
}
return mid_pos;
}
int *v;
int *stamp;
int timestamp;
void solve(int p){
++timestamp;
int mid = get_mid(p);
kill[mid] = 1;
v[0] = 0;
stamp[0] = timestamp;
for (int i=0; i<graph[mid].size(); i++) {
if(kill[graph[mid][i].second]) continue;
queue<int> q,d,p,l;
vector<int> cd1, cd2;
if(graph[mid][i].first > k) continue;
q.push(graph[mid][i].second);
d.push(graph[mid][i].first);
l.push(1);
p.push(mid);
while (!q.empty()) {
int qf = q.front();
int df = d.front();
int pf = p.front();
int lf = l.front();
cd1.push_back(df);
cd2.push_back(lf);
if(stamp[k-df] == timestamp) ret = min(v[k-df] + lf,ret);
q.pop();
d.pop();
p.pop();
l.pop();
for (int i=0; i<graph[qf].size(); i++) {
int pos = graph[qf][i].second;
if(kill[pos] || pos == pf) continue;
if(df + graph[qf][i].first > k) continue;
q.push(pos);
d.push(df + graph[qf][i].first);
p.push(qf);
l.push(lf + 1);
}
}
for (int i=0; i<cd1.size(); i++) {
if(stamp[cd1[i]] != timestamp){
v[cd1[i]] = cd2[i];
stamp[cd1[i]] = timestamp;
}
else v[cd1[i]] = min(v[cd1[i]],cd2[i]);
}
}
for (int i=0; i<graph[mid].size(); i++) {
if(kill[graph[mid][i].second]) continue;
solve(graph[mid][i].second);
}
}
int best_path(int N, int K, int H[][2], int L[]){
for (int i=0; i<N-1; i++) {
graph[H[i][0]].push_back(pi(L[i],H[i][1]));
graph[H[i][1]].push_back(pi(L[i],H[i][0]));
}
v = (int*)calloc(K+1,sizeof(int));
stamp = (int*)calloc(K+1,sizeof(int));
k = K;
solve(0);
if(ret > 1e8) return -1;
return ret;
}
Compilation message
race.cpp: In function 'int dfs(int, int)':
race.cpp:25:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
25 | for (int i=0; i<graph[p].size(); i++) {
| ~^~~~~~~~~~~~~~~~
race.cpp: In function 'int get_mid(int)':
race.cpp:36:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
36 | for (int i=0; i<new_vis.size(); i++) {
| ~^~~~~~~~~~~~~~~
race.cpp:43:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
43 | for (int i=0; i<new_vis.size(); i++) {
| ~^~~~~~~~~~~~~~~
race.cpp: In function 'void solve(int)':
race.cpp:63:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
63 | for (int i=0; i<graph[mid].size(); i++) {
| ~^~~~~~~~~~~~~~~~~~
race.cpp:84:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
84 | for (int i=0; i<graph[qf].size(); i++) {
| ~^~~~~~~~~~~~~~~~~
race.cpp:94:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
94 | for (int i=0; i<cd1.size(); i++) {
| ~^~~~~~~~~~~
race.cpp:102:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
102 | for (int i=0; i<graph[mid].size(); i++) {
| ~^~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
10076 KB |
Output is correct |
2 |
Correct |
2 ms |
10076 KB |
Output is correct |
3 |
Correct |
2 ms |
10076 KB |
Output is correct |
4 |
Correct |
3 ms |
10076 KB |
Output is correct |
5 |
Correct |
2 ms |
10076 KB |
Output is correct |
6 |
Correct |
2 ms |
10076 KB |
Output is correct |
7 |
Correct |
2 ms |
10076 KB |
Output is correct |
8 |
Correct |
2 ms |
10076 KB |
Output is correct |
9 |
Correct |
2 ms |
10076 KB |
Output is correct |
10 |
Correct |
2 ms |
10076 KB |
Output is correct |
11 |
Correct |
2 ms |
10076 KB |
Output is correct |
12 |
Correct |
2 ms |
10260 KB |
Output is correct |
13 |
Correct |
2 ms |
10076 KB |
Output is correct |
14 |
Correct |
2 ms |
10076 KB |
Output is correct |
15 |
Correct |
2 ms |
10076 KB |
Output is correct |
16 |
Correct |
2 ms |
10076 KB |
Output is correct |
17 |
Correct |
2 ms |
10076 KB |
Output is correct |
18 |
Correct |
2 ms |
10076 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
10076 KB |
Output is correct |
2 |
Correct |
2 ms |
10076 KB |
Output is correct |
3 |
Correct |
2 ms |
10076 KB |
Output is correct |
4 |
Correct |
3 ms |
10076 KB |
Output is correct |
5 |
Correct |
2 ms |
10076 KB |
Output is correct |
6 |
Correct |
2 ms |
10076 KB |
Output is correct |
7 |
Correct |
2 ms |
10076 KB |
Output is correct |
8 |
Correct |
2 ms |
10076 KB |
Output is correct |
9 |
Correct |
2 ms |
10076 KB |
Output is correct |
10 |
Correct |
2 ms |
10076 KB |
Output is correct |
11 |
Correct |
2 ms |
10076 KB |
Output is correct |
12 |
Correct |
2 ms |
10260 KB |
Output is correct |
13 |
Correct |
2 ms |
10076 KB |
Output is correct |
14 |
Correct |
2 ms |
10076 KB |
Output is correct |
15 |
Correct |
2 ms |
10076 KB |
Output is correct |
16 |
Correct |
2 ms |
10076 KB |
Output is correct |
17 |
Correct |
2 ms |
10076 KB |
Output is correct |
18 |
Correct |
2 ms |
10076 KB |
Output is correct |
19 |
Correct |
2 ms |
10076 KB |
Output is correct |
20 |
Correct |
2 ms |
10284 KB |
Output is correct |
21 |
Correct |
3 ms |
10332 KB |
Output is correct |
22 |
Correct |
5 ms |
15708 KB |
Output is correct |
23 |
Correct |
5 ms |
14428 KB |
Output is correct |
24 |
Correct |
5 ms |
15964 KB |
Output is correct |
25 |
Correct |
5 ms |
13660 KB |
Output is correct |
26 |
Correct |
4 ms |
12892 KB |
Output is correct |
27 |
Correct |
2 ms |
10332 KB |
Output is correct |
28 |
Correct |
4 ms |
11868 KB |
Output is correct |
29 |
Correct |
4 ms |
12840 KB |
Output is correct |
30 |
Correct |
4 ms |
13148 KB |
Output is correct |
31 |
Correct |
4 ms |
13916 KB |
Output is correct |
32 |
Correct |
4 ms |
13916 KB |
Output is correct |
33 |
Correct |
5 ms |
15708 KB |
Output is correct |
34 |
Correct |
5 ms |
14684 KB |
Output is correct |
35 |
Correct |
5 ms |
15964 KB |
Output is correct |
36 |
Correct |
5 ms |
17244 KB |
Output is correct |
37 |
Correct |
4 ms |
15192 KB |
Output is correct |
38 |
Correct |
4 ms |
12632 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
10076 KB |
Output is correct |
2 |
Correct |
2 ms |
10076 KB |
Output is correct |
3 |
Correct |
2 ms |
10076 KB |
Output is correct |
4 |
Correct |
3 ms |
10076 KB |
Output is correct |
5 |
Correct |
2 ms |
10076 KB |
Output is correct |
6 |
Correct |
2 ms |
10076 KB |
Output is correct |
7 |
Correct |
2 ms |
10076 KB |
Output is correct |
8 |
Correct |
2 ms |
10076 KB |
Output is correct |
9 |
Correct |
2 ms |
10076 KB |
Output is correct |
10 |
Correct |
2 ms |
10076 KB |
Output is correct |
11 |
Correct |
2 ms |
10076 KB |
Output is correct |
12 |
Correct |
2 ms |
10260 KB |
Output is correct |
13 |
Correct |
2 ms |
10076 KB |
Output is correct |
14 |
Correct |
2 ms |
10076 KB |
Output is correct |
15 |
Correct |
2 ms |
10076 KB |
Output is correct |
16 |
Correct |
2 ms |
10076 KB |
Output is correct |
17 |
Correct |
2 ms |
10076 KB |
Output is correct |
18 |
Correct |
2 ms |
10076 KB |
Output is correct |
19 |
Correct |
105 ms |
14916 KB |
Output is correct |
20 |
Correct |
103 ms |
15828 KB |
Output is correct |
21 |
Correct |
101 ms |
15832 KB |
Output is correct |
22 |
Correct |
93 ms |
16596 KB |
Output is correct |
23 |
Correct |
75 ms |
16604 KB |
Output is correct |
24 |
Correct |
52 ms |
16336 KB |
Output is correct |
25 |
Correct |
102 ms |
18640 KB |
Output is correct |
26 |
Correct |
92 ms |
21880 KB |
Output is correct |
27 |
Correct |
130 ms |
23180 KB |
Output is correct |
28 |
Correct |
177 ms |
34248 KB |
Output is correct |
29 |
Correct |
175 ms |
33736 KB |
Output is correct |
30 |
Correct |
139 ms |
23792 KB |
Output is correct |
31 |
Correct |
132 ms |
24016 KB |
Output is correct |
32 |
Correct |
136 ms |
23756 KB |
Output is correct |
33 |
Correct |
166 ms |
22796 KB |
Output is correct |
34 |
Correct |
148 ms |
23244 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
10076 KB |
Output is correct |
2 |
Correct |
2 ms |
10076 KB |
Output is correct |
3 |
Correct |
2 ms |
10076 KB |
Output is correct |
4 |
Correct |
3 ms |
10076 KB |
Output is correct |
5 |
Correct |
2 ms |
10076 KB |
Output is correct |
6 |
Correct |
2 ms |
10076 KB |
Output is correct |
7 |
Correct |
2 ms |
10076 KB |
Output is correct |
8 |
Correct |
2 ms |
10076 KB |
Output is correct |
9 |
Correct |
2 ms |
10076 KB |
Output is correct |
10 |
Correct |
2 ms |
10076 KB |
Output is correct |
11 |
Correct |
2 ms |
10076 KB |
Output is correct |
12 |
Correct |
2 ms |
10260 KB |
Output is correct |
13 |
Correct |
2 ms |
10076 KB |
Output is correct |
14 |
Correct |
2 ms |
10076 KB |
Output is correct |
15 |
Correct |
2 ms |
10076 KB |
Output is correct |
16 |
Correct |
2 ms |
10076 KB |
Output is correct |
17 |
Correct |
2 ms |
10076 KB |
Output is correct |
18 |
Correct |
2 ms |
10076 KB |
Output is correct |
19 |
Correct |
2 ms |
10076 KB |
Output is correct |
20 |
Correct |
2 ms |
10284 KB |
Output is correct |
21 |
Correct |
3 ms |
10332 KB |
Output is correct |
22 |
Correct |
5 ms |
15708 KB |
Output is correct |
23 |
Correct |
5 ms |
14428 KB |
Output is correct |
24 |
Correct |
5 ms |
15964 KB |
Output is correct |
25 |
Correct |
5 ms |
13660 KB |
Output is correct |
26 |
Correct |
4 ms |
12892 KB |
Output is correct |
27 |
Correct |
2 ms |
10332 KB |
Output is correct |
28 |
Correct |
4 ms |
11868 KB |
Output is correct |
29 |
Correct |
4 ms |
12840 KB |
Output is correct |
30 |
Correct |
4 ms |
13148 KB |
Output is correct |
31 |
Correct |
4 ms |
13916 KB |
Output is correct |
32 |
Correct |
4 ms |
13916 KB |
Output is correct |
33 |
Correct |
5 ms |
15708 KB |
Output is correct |
34 |
Correct |
5 ms |
14684 KB |
Output is correct |
35 |
Correct |
5 ms |
15964 KB |
Output is correct |
36 |
Correct |
5 ms |
17244 KB |
Output is correct |
37 |
Correct |
4 ms |
15192 KB |
Output is correct |
38 |
Correct |
4 ms |
12632 KB |
Output is correct |
39 |
Correct |
105 ms |
14916 KB |
Output is correct |
40 |
Correct |
103 ms |
15828 KB |
Output is correct |
41 |
Correct |
101 ms |
15832 KB |
Output is correct |
42 |
Correct |
93 ms |
16596 KB |
Output is correct |
43 |
Correct |
75 ms |
16604 KB |
Output is correct |
44 |
Correct |
52 ms |
16336 KB |
Output is correct |
45 |
Correct |
102 ms |
18640 KB |
Output is correct |
46 |
Correct |
92 ms |
21880 KB |
Output is correct |
47 |
Correct |
130 ms |
23180 KB |
Output is correct |
48 |
Correct |
177 ms |
34248 KB |
Output is correct |
49 |
Correct |
175 ms |
33736 KB |
Output is correct |
50 |
Correct |
139 ms |
23792 KB |
Output is correct |
51 |
Correct |
132 ms |
24016 KB |
Output is correct |
52 |
Correct |
136 ms |
23756 KB |
Output is correct |
53 |
Correct |
166 ms |
22796 KB |
Output is correct |
54 |
Correct |
148 ms |
23244 KB |
Output is correct |
55 |
Correct |
9 ms |
10844 KB |
Output is correct |
56 |
Correct |
10 ms |
10824 KB |
Output is correct |
57 |
Correct |
84 ms |
15840 KB |
Output is correct |
58 |
Correct |
43 ms |
16328 KB |
Output is correct |
59 |
Correct |
93 ms |
22740 KB |
Output is correct |
60 |
Correct |
269 ms |
40368 KB |
Output is correct |
61 |
Correct |
130 ms |
23244 KB |
Output is correct |
62 |
Correct |
146 ms |
23756 KB |
Output is correct |
63 |
Correct |
175 ms |
23760 KB |
Output is correct |
64 |
Correct |
269 ms |
25536 KB |
Output is correct |
65 |
Correct |
135 ms |
24820 KB |
Output is correct |
66 |
Correct |
266 ms |
37516 KB |
Output is correct |
67 |
Correct |
89 ms |
25940 KB |
Output is correct |
68 |
Correct |
171 ms |
30396 KB |
Output is correct |
69 |
Correct |
171 ms |
28196 KB |
Output is correct |
70 |
Correct |
163 ms |
30072 KB |
Output is correct |