# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
77164 |
2018-09-23T06:54:50 Z |
muradeyn |
Race (IOI11_race) |
C++14 |
|
348 ms |
20124 KB |
#include "race.h"
#include <bits/stdc++.h>
#define intt long long
#define FAST_READ ios_base::sync_with_stdio(0);cin.tie(0);
#define SIZE 100001
#define INF INT_MAX
#define F first
#define S second
#define in(a) scanf("%d",&a);
#define outn(a) printf("%d\n",&a);
#define outs(a) printf("%d ",&a);
using namespace std;
int root , n , k , x , y , w , used[SIZE] , dp[SIZE] , co , cent = -1 , we , ans = -1;
vector< pair<int,int> >v[SIZE];
map< int , int > mp;
bool f = true;
void init() {
for (int i = 1;i<=n;i++) {
if (used[i] < 5 && used[i] > 0)used[i] = 0;
}
}
void dfs(int s,int p) {
co++;
used[s] = 1;
int sz = v[s].size();
for (int i = 0;i<sz;i++) {
int to = v[s][i].first;
int cost = v[s][i].second;
if (to == p)continue;
if (used[to] >= 1)continue;
we += cost;
dfs(to,s);
}
}
void dfs2(int s,int p) {
used[s] = 2;
dp[s] = 1;
bool f = true;
int sz = v[s].size();
for (int i = 0;i<sz;i++) {
int to = v[s][i].first;
if (used[to] >= 2)continue;
dfs2(to,s);
if (dp[to] > co / 2) f = false;
dp[s] += dp[to];
}
if (f && cent == -1 && co - dp[s] <= co / 2) cent = s;
}
void dfs3(int s,int p,int len,int cst) {
used[s] = 3;
if (cst == k) {
if (ans == -1)ans = len;
else ans = min(ans,len);
return;
}
int sz = v[s].size();
for (int i = 0;i<sz;i++) {
int to = v[s][i].first;
int cost = v[s][i].second;
if (to == p)continue;
if (used[to] >= 3)continue;
dfs3(to,s,len + 1,cst + cost);
}
}
void dfs4(int s,int p,int len,int cst) {
used[s] = 4;
//cout<<s - 1<<" "<<cst<<" "<<k<<endl;
//char aa;
//cin>>aa;
if (cst > k)return;
if (cst == k) {
if (ans == -1)ans = len;
else ans = min(ans,len);
return;
}
else if (mp[k - cst] != 0) {
if (ans == -1)ans = len + mp[k - cst];
else ans = min(ans,len + mp[k - cst]);
}
int sz = v[s].size();
//cout<<sz<<endl;
for (int i = 0;i<sz;i++) {
int to = v[s][i].first;
int cost = v[s][i].second;
if (to == p)continue;
if (used[to] >= 4)continue;
dfs4(to,s,len + 1,cst + cost);
}
if (mp[cst] == 0)mp[cst] = len;
else if (mp[cst] > len)mp[cst] = min(mp[cst],len);
}
int best_path(int N, int K, int h[][2], int l[])
{
k = K;
n = N;
for (int i = 0;i<n - 1;i++) {
x = h[i][0];
y = h[i][1];
x++;
y++;
v[x].push_back({y,l[i]});
v[y].push_back({x,l[i]});
}
while (f) {
f = false;
init();
for (int i = 1;i<=n;i++) {
if (used[i] == 0) {
co = 0; we = 0;
dfs(i , -1);
if (we < k || co == 1) continue;
dp[i] = 0;
cent = -1;
dfs2(i,-1);
if (cent == -1)continue;
f = true;
root = cent;
dfs3(cent,-1,0,0);
mp.clear();
dfs4(cent,-1,0,0);
used[cent] = 5;
}
}
}
return ans;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
2680 KB |
Output is correct |
2 |
Correct |
4 ms |
2684 KB |
Output is correct |
3 |
Correct |
4 ms |
2744 KB |
Output is correct |
4 |
Correct |
5 ms |
2792 KB |
Output is correct |
5 |
Correct |
4 ms |
2856 KB |
Output is correct |
6 |
Correct |
4 ms |
3044 KB |
Output is correct |
7 |
Correct |
4 ms |
3044 KB |
Output is correct |
8 |
Correct |
4 ms |
3044 KB |
Output is correct |
9 |
Correct |
4 ms |
3044 KB |
Output is correct |
10 |
Correct |
4 ms |
3044 KB |
Output is correct |
11 |
Correct |
4 ms |
3044 KB |
Output is correct |
12 |
Correct |
4 ms |
3044 KB |
Output is correct |
13 |
Correct |
4 ms |
3044 KB |
Output is correct |
14 |
Correct |
4 ms |
3044 KB |
Output is correct |
15 |
Correct |
4 ms |
3044 KB |
Output is correct |
16 |
Correct |
4 ms |
3044 KB |
Output is correct |
17 |
Correct |
4 ms |
3044 KB |
Output is correct |
18 |
Correct |
5 ms |
3044 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
2680 KB |
Output is correct |
2 |
Correct |
4 ms |
2684 KB |
Output is correct |
3 |
Correct |
4 ms |
2744 KB |
Output is correct |
4 |
Correct |
5 ms |
2792 KB |
Output is correct |
5 |
Correct |
4 ms |
2856 KB |
Output is correct |
6 |
Correct |
4 ms |
3044 KB |
Output is correct |
7 |
Correct |
4 ms |
3044 KB |
Output is correct |
8 |
Correct |
4 ms |
3044 KB |
Output is correct |
9 |
Correct |
4 ms |
3044 KB |
Output is correct |
10 |
Correct |
4 ms |
3044 KB |
Output is correct |
11 |
Correct |
4 ms |
3044 KB |
Output is correct |
12 |
Correct |
4 ms |
3044 KB |
Output is correct |
13 |
Correct |
4 ms |
3044 KB |
Output is correct |
14 |
Correct |
4 ms |
3044 KB |
Output is correct |
15 |
Correct |
4 ms |
3044 KB |
Output is correct |
16 |
Correct |
4 ms |
3044 KB |
Output is correct |
17 |
Correct |
4 ms |
3044 KB |
Output is correct |
18 |
Correct |
5 ms |
3044 KB |
Output is correct |
19 |
Correct |
4 ms |
3044 KB |
Output is correct |
20 |
Correct |
4 ms |
3044 KB |
Output is correct |
21 |
Correct |
6 ms |
3052 KB |
Output is correct |
22 |
Correct |
5 ms |
3156 KB |
Output is correct |
23 |
Correct |
6 ms |
3156 KB |
Output is correct |
24 |
Correct |
5 ms |
3156 KB |
Output is correct |
25 |
Correct |
6 ms |
3156 KB |
Output is correct |
26 |
Correct |
5 ms |
3156 KB |
Output is correct |
27 |
Correct |
5 ms |
3156 KB |
Output is correct |
28 |
Correct |
6 ms |
3156 KB |
Output is correct |
29 |
Correct |
6 ms |
3156 KB |
Output is correct |
30 |
Correct |
7 ms |
3156 KB |
Output is correct |
31 |
Correct |
7 ms |
3156 KB |
Output is correct |
32 |
Correct |
6 ms |
3156 KB |
Output is correct |
33 |
Correct |
9 ms |
3156 KB |
Output is correct |
34 |
Correct |
6 ms |
3156 KB |
Output is correct |
35 |
Correct |
5 ms |
3156 KB |
Output is correct |
36 |
Correct |
5 ms |
3156 KB |
Output is correct |
37 |
Correct |
5 ms |
3184 KB |
Output is correct |
38 |
Correct |
5 ms |
3184 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
2680 KB |
Output is correct |
2 |
Correct |
4 ms |
2684 KB |
Output is correct |
3 |
Correct |
4 ms |
2744 KB |
Output is correct |
4 |
Correct |
5 ms |
2792 KB |
Output is correct |
5 |
Correct |
4 ms |
2856 KB |
Output is correct |
6 |
Correct |
4 ms |
3044 KB |
Output is correct |
7 |
Correct |
4 ms |
3044 KB |
Output is correct |
8 |
Correct |
4 ms |
3044 KB |
Output is correct |
9 |
Correct |
4 ms |
3044 KB |
Output is correct |
10 |
Correct |
4 ms |
3044 KB |
Output is correct |
11 |
Correct |
4 ms |
3044 KB |
Output is correct |
12 |
Correct |
4 ms |
3044 KB |
Output is correct |
13 |
Correct |
4 ms |
3044 KB |
Output is correct |
14 |
Correct |
4 ms |
3044 KB |
Output is correct |
15 |
Correct |
4 ms |
3044 KB |
Output is correct |
16 |
Correct |
4 ms |
3044 KB |
Output is correct |
17 |
Correct |
4 ms |
3044 KB |
Output is correct |
18 |
Correct |
5 ms |
3044 KB |
Output is correct |
19 |
Correct |
338 ms |
8700 KB |
Output is correct |
20 |
Correct |
326 ms |
8708 KB |
Output is correct |
21 |
Correct |
348 ms |
8828 KB |
Output is correct |
22 |
Correct |
346 ms |
8828 KB |
Output is correct |
23 |
Correct |
243 ms |
8860 KB |
Output is correct |
24 |
Correct |
143 ms |
10236 KB |
Output is correct |
25 |
Correct |
165 ms |
15056 KB |
Output is correct |
26 |
Correct |
107 ms |
20124 KB |
Output is correct |
27 |
Runtime error |
87 ms |
20124 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
28 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
2680 KB |
Output is correct |
2 |
Correct |
4 ms |
2684 KB |
Output is correct |
3 |
Correct |
4 ms |
2744 KB |
Output is correct |
4 |
Correct |
5 ms |
2792 KB |
Output is correct |
5 |
Correct |
4 ms |
2856 KB |
Output is correct |
6 |
Correct |
4 ms |
3044 KB |
Output is correct |
7 |
Correct |
4 ms |
3044 KB |
Output is correct |
8 |
Correct |
4 ms |
3044 KB |
Output is correct |
9 |
Correct |
4 ms |
3044 KB |
Output is correct |
10 |
Correct |
4 ms |
3044 KB |
Output is correct |
11 |
Correct |
4 ms |
3044 KB |
Output is correct |
12 |
Correct |
4 ms |
3044 KB |
Output is correct |
13 |
Correct |
4 ms |
3044 KB |
Output is correct |
14 |
Correct |
4 ms |
3044 KB |
Output is correct |
15 |
Correct |
4 ms |
3044 KB |
Output is correct |
16 |
Correct |
4 ms |
3044 KB |
Output is correct |
17 |
Correct |
4 ms |
3044 KB |
Output is correct |
18 |
Correct |
5 ms |
3044 KB |
Output is correct |
19 |
Correct |
4 ms |
3044 KB |
Output is correct |
20 |
Correct |
4 ms |
3044 KB |
Output is correct |
21 |
Correct |
6 ms |
3052 KB |
Output is correct |
22 |
Correct |
5 ms |
3156 KB |
Output is correct |
23 |
Correct |
6 ms |
3156 KB |
Output is correct |
24 |
Correct |
5 ms |
3156 KB |
Output is correct |
25 |
Correct |
6 ms |
3156 KB |
Output is correct |
26 |
Correct |
5 ms |
3156 KB |
Output is correct |
27 |
Correct |
5 ms |
3156 KB |
Output is correct |
28 |
Correct |
6 ms |
3156 KB |
Output is correct |
29 |
Correct |
6 ms |
3156 KB |
Output is correct |
30 |
Correct |
7 ms |
3156 KB |
Output is correct |
31 |
Correct |
7 ms |
3156 KB |
Output is correct |
32 |
Correct |
6 ms |
3156 KB |
Output is correct |
33 |
Correct |
9 ms |
3156 KB |
Output is correct |
34 |
Correct |
6 ms |
3156 KB |
Output is correct |
35 |
Correct |
5 ms |
3156 KB |
Output is correct |
36 |
Correct |
5 ms |
3156 KB |
Output is correct |
37 |
Correct |
5 ms |
3184 KB |
Output is correct |
38 |
Correct |
5 ms |
3184 KB |
Output is correct |
39 |
Correct |
338 ms |
8700 KB |
Output is correct |
40 |
Correct |
326 ms |
8708 KB |
Output is correct |
41 |
Correct |
348 ms |
8828 KB |
Output is correct |
42 |
Correct |
346 ms |
8828 KB |
Output is correct |
43 |
Correct |
243 ms |
8860 KB |
Output is correct |
44 |
Correct |
143 ms |
10236 KB |
Output is correct |
45 |
Correct |
165 ms |
15056 KB |
Output is correct |
46 |
Correct |
107 ms |
20124 KB |
Output is correct |
47 |
Runtime error |
87 ms |
20124 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
48 |
Halted |
0 ms |
0 KB |
- |