oj.uz

Submission #1026166

# Submission time Handle Problem Language Result Execution time Memory
1026166 2024-07-17T16:25:30 Z vanea Race (IOI11_race) C++14
43 / 100
 207 ms 37976 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int mxN = 2e5+10;
const int mxK = 1e6+10;
const int INF = 1e9+10;
int ans = INF, k, bk = 0;
int d[mxK], last[mxN];

vector<array<int, 2>> adj[mxN];

bool vis[mxN];
int sz[mxN];

void get_sz(int node, int p) {
    sz[node] = 1;
    for(auto [it, w] : adj[node]) {
        if(it == p || vis[it]) continue;
        get_sz(it, node);
        sz[node] += sz[it];
    }
}

int get_c(int node, int p, int n) {
    for(auto [it, w] : adj[node]) {
        if(vis[it] || it == p) continue;
        if(sz[it] * 2 > n) return get_c(it, node, n);
    }
    return node;
}

void get_min(int node, int p, bool filling, int dist, int s) {
    if(s > k) return ;
    if(filling) {
        if(last[s] != bk) {
            last[s] = bk;
            d[s] = dist;
        }
        else {
            d[s] = min(d[s], dist);
        }
    }
    else {
        if(last[k-s] == bk) {
            ans = min(ans, dist+d[k-s]);
        }
    }
    for(auto [it, w] : adj[node]) {
        if(it == p || vis[it]) continue;
        get_min(it, node, filling, dist+1, s+w);
    }
}

void build(int node) {
    get_sz(node, -1);
    int c = get_c(node, -1, sz[node]);
    vis[c] = true;
    bk++;
    last[0] = bk;
    for(auto [it, w] : adj[c]) {
        if(vis[it]) continue;
        get_min(it, c, 0, 1, w);
        get_min(it, c, 1, 1, w);
    }
    for(auto [it, w] : adj[c]) {
        if(vis[it]) continue;
        build(it);
    }
}

int best_path(int n, int K, int h[][2], int l[]) {
    for(int i = 0; i < n-1; i++) {
        adj[h[i][0]].push_back({h[i][1], l[i]});
        adj[h[i][1]].push_back({h[i][0], l[i]});
    }
    k = K;
    build(0);
    return (ans == INF ? -1 : ans);
}
/*
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout << best_path(11, 12, {{0, 1}, {0, 2}, {2, 3}, {3, 4}, {4, 5}, {0, 6},
                      {6, 7}, {6, 8}, {8, 9}, {8, 10}},
                      {3, 4, 5, 4, 6, 3, 2, 5, 6, 7});
}*/

Compilation message

race.cpp: In function 'void get_sz(int, int)':
race.cpp:18:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   18 |     for(auto [it, w] : adj[node]) {
      |              ^
race.cpp: In function 'int get_c(int, int, int)':
race.cpp:26:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   26 |     for(auto [it, w] : adj[node]) {
      |              ^
race.cpp: In function 'void get_min(int, int, bool, int, int)':
race.cpp:49:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   49 |     for(auto [it, w] : adj[node]) {
      |              ^
race.cpp: In function 'void build(int)':
race.cpp:61:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   61 |     for(auto [it, w] : adj[c]) {
      |              ^
race.cpp:66:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   66 |     for(auto [it, w] : adj[c]) {
      |              ^

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 10584 KB Output is correct
2 Correct 1 ms 10588 KB Output is correct
3 Correct 1 ms 10588 KB Output is correct
4 Correct 1 ms 10588 KB Output is correct
5 Correct 1 ms 10588 KB Output is correct
6 Correct 1 ms 10596 KB Output is correct
7 Correct 1 ms 10588 KB Output is correct
8 Correct 1 ms 10588 KB Output is correct
9 Correct 1 ms 10588 KB Output is correct
10 Correct 1 ms 10584 KB Output is correct
11 Correct 2 ms 10584 KB Output is correct
12 Correct 1 ms 10684 KB Output is correct
13 Correct 2 ms 10588 KB Output is correct
14 Correct 1 ms 10588 KB Output is correct
15 Correct 2 ms 10584 KB Output is correct
16 Correct 2 ms 10588 KB Output is correct
17 Correct 1 ms 10588 KB Output is correct
18 Correct 1 ms 10588 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 10584 KB Output is correct
2 Correct 1 ms 10588 KB Output is correct
3 Correct 1 ms 10588 KB Output is correct
4 Correct 1 ms 10588 KB Output is correct
5 Correct 1 ms 10588 KB Output is correct
6 Correct 1 ms 10596 KB Output is correct
7 Correct 1 ms 10588 KB Output is correct
8 Correct 1 ms 10588 KB Output is correct
9 Correct 1 ms 10588 KB Output is correct
10 Correct 1 ms 10584 KB Output is correct
11 Correct 2 ms 10584 KB Output is correct
12 Correct 1 ms 10684 KB Output is correct
13 Correct 2 ms 10588 KB Output is correct
14 Correct 1 ms 10588 KB Output is correct
15 Correct 2 ms 10584 KB Output is correct
16 Correct 2 ms 10588 KB Output is correct
17 Correct 1 ms 10588 KB Output is correct
18 Correct 1 ms 10588 KB Output is correct
19 Correct 1 ms 10588 KB Output is correct
20 Correct 1 ms 10588 KB Output is correct
21 Correct 2 ms 10584 KB Output is correct
22 Correct 3 ms 13660 KB Output is correct
23 Correct 2 ms 13148 KB Output is correct
24 Correct 4 ms 13660 KB Output is correct
25 Correct 3 ms 12380 KB Output is correct
26 Correct 3 ms 11868 KB Output is correct
27 Correct 2 ms 10588 KB Output is correct
28 Correct 2 ms 12636 KB Output is correct
29 Correct 2 ms 11612 KB Output is correct
30 Correct 2 ms 11868 KB Output is correct
31 Correct 3 ms 12392 KB Output is correct
32 Correct 3 ms 12380 KB Output is correct
33 Correct 3 ms 13148 KB Output is correct
34 Correct 2 ms 12636 KB Output is correct
35 Correct 3 ms 13404 KB Output is correct
36 Correct 3 ms 13916 KB Output is correct
37 Correct 2 ms 12380 KB Output is correct
38 Correct 2 ms 11612 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 10584 KB Output is correct
2 Correct 1 ms 10588 KB Output is correct
3 Correct 1 ms 10588 KB Output is correct
4 Correct 1 ms 10588 KB Output is correct
5 Correct 1 ms 10588 KB Output is correct
6 Correct 1 ms 10596 KB Output is correct
7 Correct 1 ms 10588 KB Output is correct
8 Correct 1 ms 10588 KB Output is correct
9 Correct 1 ms 10588 KB Output is correct
10 Correct 1 ms 10584 KB Output is correct
11 Correct 2 ms 10584 KB Output is correct
12 Correct 1 ms 10684 KB Output is correct
13 Correct 2 ms 10588 KB Output is correct
14 Correct 1 ms 10588 KB Output is correct
15 Correct 2 ms 10584 KB Output is correct
16 Correct 2 ms 10588 KB Output is correct
17 Correct 1 ms 10588 KB Output is correct
18 Correct 1 ms 10588 KB Output is correct
19 Correct 68 ms 16368 KB Output is correct
20 Correct 66 ms 16476 KB Output is correct
21 Correct 71 ms 16464 KB Output is correct
22 Correct 63 ms 16472 KB Output is correct
23 Correct 38 ms 16724 KB Output is correct
24 Correct 32 ms 16504 KB Output is correct
25 Correct 87 ms 20156 KB Output is correct
26 Correct 62 ms 24656 KB Output is correct
27 Correct 83 ms 21844 KB Output is correct
28 Correct 129 ms 36320 KB Output is correct
29 Correct 136 ms 35412 KB Output is correct
30 Correct 82 ms 22608 KB Output is correct
31 Correct 84 ms 22444 KB Output is correct
32 Correct 87 ms 22396 KB Output is correct
33 Correct 113 ms 21524 KB Output is correct
34 Correct 108 ms 21844 KB Output is correct

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 10584 KB Output is correct
2 Correct 1 ms 10588 KB Output is correct
3 Correct 1 ms 10588 KB Output is correct
4 Correct 1 ms 10588 KB Output is correct
5 Correct 1 ms 10588 KB Output is correct
6 Correct 1 ms 10596 KB Output is correct
7 Correct 1 ms 10588 KB Output is correct
8 Correct 1 ms 10588 KB Output is correct
9 Correct 1 ms 10588 KB Output is correct
10 Correct 1 ms 10584 KB Output is correct
11 Correct 2 ms 10584 KB Output is correct
12 Correct 1 ms 10684 KB Output is correct
13 Correct 2 ms 10588 KB Output is correct
14 Correct 1 ms 10588 KB Output is correct
15 Correct 2 ms 10584 KB Output is correct
16 Correct 2 ms 10588 KB Output is correct
17 Correct 1 ms 10588 KB Output is correct
18 Correct 1 ms 10588 KB Output is correct
19 Correct 1 ms 10588 KB Output is correct
20 Correct 1 ms 10588 KB Output is correct
21 Correct 2 ms 10584 KB Output is correct
22 Correct 3 ms 13660 KB Output is correct
23 Correct 2 ms 13148 KB Output is correct
24 Correct 4 ms 13660 KB Output is correct
25 Correct 3 ms 12380 KB Output is correct
26 Correct 3 ms 11868 KB Output is correct
27 Correct 2 ms 10588 KB Output is correct
28 Correct 2 ms 12636 KB Output is correct
29 Correct 2 ms 11612 KB Output is correct
30 Correct 2 ms 11868 KB Output is correct
31 Correct 3 ms 12392 KB Output is correct
32 Correct 3 ms 12380 KB Output is correct
33 Correct 3 ms 13148 KB Output is correct
34 Correct 2 ms 12636 KB Output is correct
35 Correct 3 ms 13404 KB Output is correct
36 Correct 3 ms 13916 KB Output is correct
37 Correct 2 ms 12380 KB Output is correct
38 Correct 2 ms 11612 KB Output is correct
39 Correct 68 ms 16368 KB Output is correct
40 Correct 66 ms 16476 KB Output is correct
41 Correct 71 ms 16464 KB Output is correct
42 Correct 63 ms 16472 KB Output is correct
43 Correct 38 ms 16724 KB Output is correct
44 Correct 32 ms 16504 KB Output is correct
45 Correct 87 ms 20156 KB Output is correct
46 Correct 62 ms 24656 KB Output is correct
47 Correct 83 ms 21844 KB Output is correct
48 Correct 129 ms 36320 KB Output is correct
49 Correct 136 ms 35412 KB Output is correct
50 Correct 82 ms 22608 KB Output is correct
51 Correct 84 ms 22444 KB Output is correct
52 Correct 87 ms 22396 KB Output is correct
53 Correct 113 ms 21524 KB Output is correct
54 Correct 108 ms 21844 KB Output is correct
55 Correct 6 ms 10980 KB Output is correct
56 Correct 6 ms 11100 KB Output is correct
57 Correct 42 ms 17036 KB Output is correct
58 Correct 20 ms 17872 KB Output is correct
59 Correct 60 ms 26708 KB Output is correct
60 Incorrect 207 ms 37976 KB Output isn't correct
61 Halted 0 ms 0 KB -