oj.uz

Submission #109676

# Submission time Handle Problem Language Result Execution time Memory
109676 2019-05-07T11:16:40 Z someone_aa Race (IOI11_race) C++17
21 / 100
 3000 ms 15940 KB 
#include <bits/stdc++.h>
#include "race.h"
#define ll long long
#define pb push_back
#define mp make_pair
using namespace std;
const int maxn = 200100;
const int maxk = 1100000;

vector<pair<int,int> > g[maxn];
bool deleted[maxn];
int sbtsum[maxn], parent[maxn];
int n, k;

class path {
public:
    int node, sum, cnt;
};

vector<path> curr_paths;
void find_paths(int node, int p, int sum, int cnt) {
    curr_paths.pb({node, sum, cnt});
    for(auto i:g[node]) {
        if(deleted[i.first] || i.first == p) continue;
        find_paths(i.first, node, sum+i.second, cnt+1);
    }
}

int min_cnt[maxk];
int result;

void solve(int node) {
    memset(min_cnt,0,sizeof(min_cnt));
    for(auto i:g[node]) {
        if(deleted[i.first]) continue;
        curr_paths.clear();
        find_paths(i.first, -1, 0, 0);

        for(auto j:curr_paths) {
            int curr = j.sum + i.second;

            if(curr > k) continue;
            else if(curr == k) result = min(result, j.cnt+1);
            else {
                int diff = k - curr;
                if(min_cnt[diff] != 0) result = min(result, min_cnt[diff] + j.cnt + 1);
            }
        }

        for(auto j:curr_paths) {
            int curr = j.sum + i.second;

            if(curr > k) continue;

            int newval = j.cnt + 1;
            if(min_cnt[curr] == 0) min_cnt[curr] = newval;
            else min_cnt[curr] = min(min_cnt[curr], newval);
        }
    }
}

void dfs0(int node, int p) {
    sbtsum[node] = 1;
    parent[node] = p;
    for(auto i:g[node]) {
        if(deleted[i.first] || i.first == p) continue;
        dfs0(i.first, node);
        sbtsum[node] += sbtsum[i.first];
    }
}

void decompose(int node) {
    dfs0(node, -1);

    int best_size = sbtsum[node];
    int centroid = node;

    queue<int>q;
    q.push(node);

    while(!q.empty()) {
        int curr = q.front();
        q.pop();

        int curr_size = sbtsum[node] - sbtsum[curr];
        for(auto i:g[curr]) {
            if(deleted[i.first] || parent[i.first] != curr) continue;
            curr_size = max(curr_size, sbtsum[i.first]);
            q.push(i.first);
        }

        if(curr_size < best_size) {
            best_size = curr_size;
            centroid = curr;
        }
    }

    deleted[centroid] = true;
    solve(centroid);
    for(auto i:g[centroid]) {
        if(deleted[i.first]) continue;
        decompose(i.first);
    }
}

int best_path(int N, int K, int H[][2], int L[]) {
    n = N; k = K;
    result = INT_MAX;
    for(int i=0;i<N-1;i++) {
        int a = H[i][0];
        int b = H[i][1];
        int c = L[i];

        g[a].pb(mp(b, c));
        g[b].pb(mp(a, c));
    }

    decompose(0);
    if(result == INT_MAX) return -1;
    return result;
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 9344 KB Output is correct
2 Correct 31 ms 9344 KB Output is correct
3 Correct 32 ms 9344 KB Output is correct
4 Correct 32 ms 9344 KB Output is correct
5 Correct 35 ms 9344 KB Output is correct
6 Correct 35 ms 9340 KB Output is correct
7 Correct 33 ms 9300 KB Output is correct
8 Correct 35 ms 9412 KB Output is correct
9 Correct 31 ms 9344 KB Output is correct
10 Correct 32 ms 9404 KB Output is correct
11 Correct 33 ms 9344 KB Output is correct
12 Correct 32 ms 9344 KB Output is correct
13 Correct 35 ms 9344 KB Output is correct
14 Correct 29 ms 9344 KB Output is correct
15 Correct 31 ms 9344 KB Output is correct
16 Correct 32 ms 9344 KB Output is correct
17 Correct 35 ms 9344 KB Output is correct
18 Correct 35 ms 9344 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 9344 KB Output is correct
2 Correct 31 ms 9344 KB Output is correct
3 Correct 32 ms 9344 KB Output is correct
4 Correct 32 ms 9344 KB Output is correct
5 Correct 35 ms 9344 KB Output is correct
6 Correct 35 ms 9340 KB Output is correct
7 Correct 33 ms 9300 KB Output is correct
8 Correct 35 ms 9412 KB Output is correct
9 Correct 31 ms 9344 KB Output is correct
10 Correct 32 ms 9404 KB Output is correct
11 Correct 33 ms 9344 KB Output is correct
12 Correct 32 ms 9344 KB Output is correct
13 Correct 35 ms 9344 KB Output is correct
14 Correct 29 ms 9344 KB Output is correct
15 Correct 31 ms 9344 KB Output is correct
16 Correct 32 ms 9344 KB Output is correct
17 Correct 35 ms 9344 KB Output is correct
18 Correct 35 ms 9344 KB Output is correct
19 Correct 13 ms 9344 KB Output is correct
20 Correct 35 ms 9344 KB Output is correct
21 Correct 251 ms 9464 KB Output is correct
22 Correct 269 ms 9336 KB Output is correct
23 Correct 235 ms 9456 KB Output is correct
24 Correct 225 ms 9472 KB Output is correct
25 Correct 254 ms 9472 KB Output is correct
26 Correct 208 ms 9472 KB Output is correct
27 Correct 201 ms 9468 KB Output is correct
28 Correct 209 ms 9472 KB Output is correct
29 Correct 225 ms 9468 KB Output is correct
30 Correct 218 ms 9464 KB Output is correct
31 Correct 213 ms 9344 KB Output is correct
32 Correct 219 ms 9464 KB Output is correct
33 Correct 234 ms 9452 KB Output is correct
34 Correct 199 ms 9492 KB Output is correct
35 Correct 231 ms 9592 KB Output is correct
36 Correct 186 ms 9472 KB Output is correct
37 Correct 182 ms 9548 KB Output is correct
38 Correct 193 ms 9500 KB Output is correct

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 9344 KB Output is correct
2 Correct 31 ms 9344 KB Output is correct
3 Correct 32 ms 9344 KB Output is correct
4 Correct 32 ms 9344 KB Output is correct
5 Correct 35 ms 9344 KB Output is correct
6 Correct 35 ms 9340 KB Output is correct
7 Correct 33 ms 9300 KB Output is correct
8 Correct 35 ms 9412 KB Output is correct
9 Correct 31 ms 9344 KB Output is correct
10 Correct 32 ms 9404 KB Output is correct
11 Correct 33 ms 9344 KB Output is correct
12 Correct 32 ms 9344 KB Output is correct
13 Correct 35 ms 9344 KB Output is correct
14 Correct 29 ms 9344 KB Output is correct
15 Correct 31 ms 9344 KB Output is correct
16 Correct 32 ms 9344 KB Output is correct
17 Correct 35 ms 9344 KB Output is correct
18 Correct 35 ms 9344 KB Output is correct
19 Execution timed out 3015 ms 15940 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 9344 KB Output is correct
2 Correct 31 ms 9344 KB Output is correct
3 Correct 32 ms 9344 KB Output is correct
4 Correct 32 ms 9344 KB Output is correct
5 Correct 35 ms 9344 KB Output is correct
6 Correct 35 ms 9340 KB Output is correct
7 Correct 33 ms 9300 KB Output is correct
8 Correct 35 ms 9412 KB Output is correct
9 Correct 31 ms 9344 KB Output is correct
10 Correct 32 ms 9404 KB Output is correct
11 Correct 33 ms 9344 KB Output is correct
12 Correct 32 ms 9344 KB Output is correct
13 Correct 35 ms 9344 KB Output is correct
14 Correct 29 ms 9344 KB Output is correct
15 Correct 31 ms 9344 KB Output is correct
16 Correct 32 ms 9344 KB Output is correct
17 Correct 35 ms 9344 KB Output is correct
18 Correct 35 ms 9344 KB Output is correct
19 Correct 13 ms 9344 KB Output is correct
20 Correct 35 ms 9344 KB Output is correct
21 Correct 251 ms 9464 KB Output is correct
22 Correct 269 ms 9336 KB Output is correct
23 Correct 235 ms 9456 KB Output is correct
24 Correct 225 ms 9472 KB Output is correct
25 Correct 254 ms 9472 KB Output is correct
26 Correct 208 ms 9472 KB Output is correct
27 Correct 201 ms 9468 KB Output is correct
28 Correct 209 ms 9472 KB Output is correct
29 Correct 225 ms 9468 KB Output is correct
30 Correct 218 ms 9464 KB Output is correct
31 Correct 213 ms 9344 KB Output is correct
32 Correct 219 ms 9464 KB Output is correct
33 Correct 234 ms 9452 KB Output is correct
34 Correct 199 ms 9492 KB Output is correct
35 Correct 231 ms 9592 KB Output is correct
36 Correct 186 ms 9472 KB Output is correct
37 Correct 182 ms 9548 KB Output is correct
38 Correct 193 ms 9500 KB Output is correct
39 Execution timed out 3015 ms 15940 KB Time limit exceeded
40 Halted 0 ms 0 KB -