oj.uz

Submission #429463

# Submission time Handle Problem Language Result Execution time Memory
429463 2021-06-16T00:31:37 Z Odavey Race (IOI11_race) C++17
21 / 100
 589 ms 39856 KB 
//
// ~oisín~ C++ Template
//

#include                <bits/stdc++.h>
#define MX_N            200005
#define mp              make_pair
#define mod7            1000000007
#define modpi           314159
#define PI              3.141592653589793238
#define pb              push_back
#define FastIO          ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define All(a)          a.begin(),a.end()
#define fi              first
#define se              second
#define ll              long long int
#define ull             unsigned long long int

int kx[8]  =            {+2, +2, -2, -2, +1, +1, -1, -1};
int ky[8]  =            {+1, -1, +1, -1, +2, -2, +2, -2};
int d9x[9] =            {+1, +1, +1, +0, +0, +0, -1, -1, -1};
int d9y[9] =            {+1, +0, -1, +1, +0, -1, +1, +0, -1};
int dx4[4] =            {+0, +0, +1, -1};
int dy4[4] =            {+1, -1, +0, +0};

ll gcd(ull a, ull b){
    return (a==0)?b:gcd(b%a,a);
}

ll lcm(ull a, ull b){
    return a*(b/gcd(a,b));
}

const long long INF = 1e18;

using namespace std;

map<ll, bool> d_b;
map<ll, int> d_id;
map<int, int> l_q[MX_N];

ll k;

bool is_heavy[MX_N];
int card[MX_N], p[MX_N], heavy[MX_N], l[MX_N], tin[MX_N], tout[MX_N], whom[MX_N*2];
ll depth[MX_N];
int gl_tit = 0;
int gl_dit = 0;

vector<pair<int, ll> > adj[MX_N];

void info_dfs(int at){
    whom[gl_tit] = at;
    tin[at] = gl_tit++;
    card[at] = 1;
    for(auto& [to, w] : adj[at]){
        if(p[at] == to){
            continue;
        }
        p[to] = at;
        l[to] = l[at] + 1;
        depth[to] = depth[at] + w;
        info_dfs(to);
        card[at] += card[to];
        if(heavy[at] == -1){
            heavy[at] = to;
        }else{
            if(card[to] >= card[heavy[at]]){
                heavy[at] = to;
            }
        }
    }
    if(heavy[at] != -1){
        is_heavy[heavy[at]] = true;
    }
    whom[gl_tit] = -1;
    tout[at] = gl_tit++;
    return;
}

int ans = 1000000009;

void dfs(int at){
    for(auto& [to, w] : adj[at]){
        if(to == p[at] || is_heavy[to]){
            continue;
        }
        dfs(to);
    }
    if(heavy[at] != -1){
        dfs(heavy[at]);
    }
    for(auto& [to, w] : adj[at]){
        if(to == p[at] || is_heavy[to]){
            continue;
        }
        for(int i=tin[to];i<=tout[to];++i){
            if(whom[i] == -1){
                continue;
            }
            if(d_b[depth[whom[i]]] == false){
                l_q[gl_dit][l[whom[i]]]++;
                d_id[depth[whom[i]]] = gl_dit++;
                d_b[depth[whom[i]]] = true;
            }else{
                int tmp_it = d_id[depth[whom[i]]];
                l_q[tmp_it][l[whom[i]]]++;
            }
        }
    }
    if(d_b[depth[at]] == false){
        l_q[gl_dit][l[at]]++;
        d_id[depth[at]] = gl_dit++;
        d_b[depth[at]] = true;
    }else{
        int tmp_it = d_id[depth[at]];
        l_q[tmp_it][l[at]]++;
    }

    for(auto& [to, w] : adj[at]){
        if(to == p[at] || is_heavy[to]){
            continue;
        }
        for(int i=tin[to];i<=tout[to];++i){
            if(whom[i] == -1){
                continue;
            }
            int a = whom[i];
            ll db = k + 2ll*depth[at] - depth[a];
            if(d_b[db] == false){
                continue;
            }
            int tmp_id = d_id[db];
            if(l_q[tmp_id].empty()){
                continue;
            }
            int lb = l_q[tmp_id].begin()->first;
            if(((lb == l[a]) && (l_q[tmp_id][lb] == 1) && depth[a] == db) || (l_q[tmp_id][lb] == 0)){
                continue;
            }
            ans = min(ans, l[a] + lb - 2*l[at]);
        }
    }

    int a = at;
    int tmp_id, lb;
    ll db = k + 2ll*depth[at] - depth[a];
    if(d_b[db] == false){
        goto crime;
    }
    tmp_id = d_id[db];
    if(l_q[tmp_id].empty()){
        goto crime;
    }
    lb = l_q[tmp_id].begin()->first;
    if(((lb == l[a]) && (l_q[tmp_id][lb] == 1) && depth[a] == db) || (l_q[tmp_id][lb] == 0)){
        goto crime;
    }
    ans = min(ans, l[a] + lb - 2*l[at]);

    crime:

    if(!is_heavy[at]){
        for(int i=tin[at];i<=tout[at];++i){
            if(whom[i] == -1){
                continue;
            }
            int tmp_it = d_id[depth[whom[i]]];
            l_q[tmp_it][l[whom[i]]]--;
        }
    }
    return;
}

int best_path(int N, int K, int H[][2], int L[]){
    for(int i=0;i<N-1;++i){
        int u = H[i][0], v = H[i][1];
        ll w = L[i];
        adj[u].pb({v, w});
        adj[v].pb({u, w});
    }
    memset(p, -1, sizeof(p));
    memset(heavy, -1, sizeof(heavy));
    memset(is_heavy, 0, sizeof(is_heavy));
    k = K;
    l[0] = 0;
    depth[0] = 0ll;
    info_dfs(0);
    dfs(0);
    if(ans == 1000000009){
        return -1;
    }else{
        return ans;
    }
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 16204 KB Output is correct
2 Correct 11 ms 16132 KB Output is correct
3 Correct 11 ms 16204 KB Output is correct
4 Correct 12 ms 16204 KB Output is correct
5 Correct 12 ms 16204 KB Output is correct
6 Correct 12 ms 16204 KB Output is correct
7 Correct 11 ms 16188 KB Output is correct
8 Correct 11 ms 16192 KB Output is correct
9 Correct 11 ms 16204 KB Output is correct
10 Correct 12 ms 16204 KB Output is correct
11 Correct 11 ms 16204 KB Output is correct
12 Correct 11 ms 16204 KB Output is correct
13 Correct 11 ms 16204 KB Output is correct
14 Correct 11 ms 16156 KB Output is correct
15 Correct 11 ms 16204 KB Output is correct
16 Correct 12 ms 16204 KB Output is correct
17 Correct 13 ms 16204 KB Output is correct
18 Correct 11 ms 16232 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 16204 KB Output is correct
2 Correct 11 ms 16132 KB Output is correct
3 Correct 11 ms 16204 KB Output is correct
4 Correct 12 ms 16204 KB Output is correct
5 Correct 12 ms 16204 KB Output is correct
6 Correct 12 ms 16204 KB Output is correct
7 Correct 11 ms 16188 KB Output is correct
8 Correct 11 ms 16192 KB Output is correct
9 Correct 11 ms 16204 KB Output is correct
10 Correct 12 ms 16204 KB Output is correct
11 Correct 11 ms 16204 KB Output is correct
12 Correct 11 ms 16204 KB Output is correct
13 Correct 11 ms 16204 KB Output is correct
14 Correct 11 ms 16156 KB Output is correct
15 Correct 11 ms 16204 KB Output is correct
16 Correct 12 ms 16204 KB Output is correct
17 Correct 13 ms 16204 KB Output is correct
18 Correct 11 ms 16232 KB Output is correct
19 Correct 13 ms 16160 KB Output is correct
20 Correct 12 ms 16204 KB Output is correct
21 Correct 13 ms 16420 KB Output is correct
22 Correct 15 ms 16588 KB Output is correct
23 Correct 14 ms 16648 KB Output is correct
24 Correct 16 ms 16596 KB Output is correct
25 Correct 14 ms 16552 KB Output is correct
26 Correct 16 ms 16568 KB Output is correct
27 Correct 15 ms 16204 KB Output is correct
28 Correct 15 ms 16540 KB Output is correct
29 Correct 14 ms 16588 KB Output is correct
30 Correct 14 ms 16660 KB Output is correct
31 Correct 14 ms 16564 KB Output is correct
32 Correct 14 ms 16588 KB Output is correct
33 Correct 16 ms 16676 KB Output is correct
34 Correct 14 ms 16528 KB Output is correct
35 Correct 13 ms 16512 KB Output is correct
36 Correct 12 ms 16460 KB Output is correct
37 Correct 13 ms 16536 KB Output is correct
38 Correct 14 ms 16476 KB Output is correct

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 16204 KB Output is correct
2 Correct 11 ms 16132 KB Output is correct
3 Correct 11 ms 16204 KB Output is correct
4 Correct 12 ms 16204 KB Output is correct
5 Correct 12 ms 16204 KB Output is correct
6 Correct 12 ms 16204 KB Output is correct
7 Correct 11 ms 16188 KB Output is correct
8 Correct 11 ms 16192 KB Output is correct
9 Correct 11 ms 16204 KB Output is correct
10 Correct 12 ms 16204 KB Output is correct
11 Correct 11 ms 16204 KB Output is correct
12 Correct 11 ms 16204 KB Output is correct
13 Correct 11 ms 16204 KB Output is correct
14 Correct 11 ms 16156 KB Output is correct
15 Correct 11 ms 16204 KB Output is correct
16 Correct 12 ms 16204 KB Output is correct
17 Correct 13 ms 16204 KB Output is correct
18 Correct 11 ms 16232 KB Output is correct
19 Correct 292 ms 25832 KB Output is correct
20 Correct 278 ms 25824 KB Output is correct
21 Correct 293 ms 25732 KB Output is correct
22 Correct 267 ms 25640 KB Output is correct
23 Correct 589 ms 26500 KB Output is correct
24 Correct 305 ms 25376 KB Output is correct
25 Incorrect 182 ms 39856 KB Output isn't correct
26 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 16204 KB Output is correct
2 Correct 11 ms 16132 KB Output is correct
3 Correct 11 ms 16204 KB Output is correct
4 Correct 12 ms 16204 KB Output is correct
5 Correct 12 ms 16204 KB Output is correct
6 Correct 12 ms 16204 KB Output is correct
7 Correct 11 ms 16188 KB Output is correct
8 Correct 11 ms 16192 KB Output is correct
9 Correct 11 ms 16204 KB Output is correct
10 Correct 12 ms 16204 KB Output is correct
11 Correct 11 ms 16204 KB Output is correct
12 Correct 11 ms 16204 KB Output is correct
13 Correct 11 ms 16204 KB Output is correct
14 Correct 11 ms 16156 KB Output is correct
15 Correct 11 ms 16204 KB Output is correct
16 Correct 12 ms 16204 KB Output is correct
17 Correct 13 ms 16204 KB Output is correct
18 Correct 11 ms 16232 KB Output is correct
19 Correct 13 ms 16160 KB Output is correct
20 Correct 12 ms 16204 KB Output is correct
21 Correct 13 ms 16420 KB Output is correct
22 Correct 15 ms 16588 KB Output is correct
23 Correct 14 ms 16648 KB Output is correct
24 Correct 16 ms 16596 KB Output is correct
25 Correct 14 ms 16552 KB Output is correct
26 Correct 16 ms 16568 KB Output is correct
27 Correct 15 ms 16204 KB Output is correct
28 Correct 15 ms 16540 KB Output is correct
29 Correct 14 ms 16588 KB Output is correct
30 Correct 14 ms 16660 KB Output is correct
31 Correct 14 ms 16564 KB Output is correct
32 Correct 14 ms 16588 KB Output is correct
33 Correct 16 ms 16676 KB Output is correct
34 Correct 14 ms 16528 KB Output is correct
35 Correct 13 ms 16512 KB Output is correct
36 Correct 12 ms 16460 KB Output is correct
37 Correct 13 ms 16536 KB Output is correct
38 Correct 14 ms 16476 KB Output is correct
39 Correct 292 ms 25832 KB Output is correct
40 Correct 278 ms 25824 KB Output is correct
41 Correct 293 ms 25732 KB Output is correct
42 Correct 267 ms 25640 KB Output is correct
43 Correct 589 ms 26500 KB Output is correct
44 Correct 305 ms 25376 KB Output is correct
45 Incorrect 182 ms 39856 KB Output isn't correct
46 Halted 0 ms 0 KB -