oj.uz

Submission #429453

# Submission time Handle Problem Language Result Execution time Memory
429453 2021-06-16T00:12:56 Z Odavey Race (IOI11_race) C++17
21 / 100
 474 ms 39364 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;
        heavy[at] = -1;
        is_heavy[at] = false;
        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;
                }
                //cout << "With god as my witness, a = " << a << ", db & lb = " << db << " & " << lb << ", giving " << l[a] + lb - 2*l[at] << " length(s)\n";
                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;
        }
        //cout << "With god as my witness, a = " << a << ", db & lb = " << db << " & " << lb << ", giving " << l[a] + lb - 2*l[at] << " length(s)\n";
        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(heavy, -1, sizeof(heavy));
        k = K;
        l[0] = 0;
        depth[0] = 0;
        info_dfs(0);
        dfs(0);
      	if(ans == 1000000009){
          	return -1;
        }
        return ans;
    }

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 15180 KB Output is correct
2 Correct 11 ms 15176 KB Output is correct
3 Correct 10 ms 15180 KB Output is correct
4 Correct 11 ms 15252 KB Output is correct
5 Correct 10 ms 15168 KB Output is correct
6 Correct 11 ms 15256 KB Output is correct
7 Correct 11 ms 15180 KB Output is correct
8 Correct 11 ms 15272 KB Output is correct
9 Correct 11 ms 15196 KB Output is correct
10 Correct 11 ms 15180 KB Output is correct
11 Correct 10 ms 15180 KB Output is correct
12 Correct 12 ms 15276 KB Output is correct
13 Correct 11 ms 15180 KB Output is correct
14 Correct 12 ms 15184 KB Output is correct
15 Correct 11 ms 15152 KB Output is correct
16 Correct 12 ms 15188 KB Output is correct
17 Correct 11 ms 15180 KB Output is correct
18 Correct 11 ms 15180 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 15180 KB Output is correct
2 Correct 11 ms 15176 KB Output is correct
3 Correct 10 ms 15180 KB Output is correct
4 Correct 11 ms 15252 KB Output is correct
5 Correct 10 ms 15168 KB Output is correct
6 Correct 11 ms 15256 KB Output is correct
7 Correct 11 ms 15180 KB Output is correct
8 Correct 11 ms 15272 KB Output is correct
9 Correct 11 ms 15196 KB Output is correct
10 Correct 11 ms 15180 KB Output is correct
11 Correct 10 ms 15180 KB Output is correct
12 Correct 12 ms 15276 KB Output is correct
13 Correct 11 ms 15180 KB Output is correct
14 Correct 12 ms 15184 KB Output is correct
15 Correct 11 ms 15152 KB Output is correct
16 Correct 12 ms 15188 KB Output is correct
17 Correct 11 ms 15180 KB Output is correct
18 Correct 11 ms 15180 KB Output is correct
19 Correct 11 ms 15180 KB Output is correct
20 Correct 11 ms 15212 KB Output is correct
21 Correct 12 ms 15436 KB Output is correct
22 Correct 14 ms 15700 KB Output is correct
23 Correct 13 ms 15672 KB Output is correct
24 Correct 13 ms 15564 KB Output is correct
25 Correct 13 ms 15692 KB Output is correct
26 Correct 14 ms 15692 KB Output is correct
27 Correct 11 ms 15336 KB Output is correct
28 Correct 13 ms 15692 KB Output is correct
29 Correct 13 ms 15692 KB Output is correct
30 Correct 14 ms 15692 KB Output is correct
31 Correct 14 ms 15692 KB Output is correct
32 Correct 13 ms 15692 KB Output is correct
33 Correct 14 ms 15680 KB Output is correct
34 Correct 13 ms 15564 KB Output is correct
35 Correct 12 ms 15588 KB Output is correct
36 Correct 12 ms 15564 KB Output is correct
37 Correct 12 ms 15564 KB Output is correct
38 Correct 13 ms 15604 KB Output is correct

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 15180 KB Output is correct
2 Correct 11 ms 15176 KB Output is correct
3 Correct 10 ms 15180 KB Output is correct
4 Correct 11 ms 15252 KB Output is correct
5 Correct 10 ms 15168 KB Output is correct
6 Correct 11 ms 15256 KB Output is correct
7 Correct 11 ms 15180 KB Output is correct
8 Correct 11 ms 15272 KB Output is correct
9 Correct 11 ms 15196 KB Output is correct
10 Correct 11 ms 15180 KB Output is correct
11 Correct 10 ms 15180 KB Output is correct
12 Correct 12 ms 15276 KB Output is correct
13 Correct 11 ms 15180 KB Output is correct
14 Correct 12 ms 15184 KB Output is correct
15 Correct 11 ms 15152 KB Output is correct
16 Correct 12 ms 15188 KB Output is correct
17 Correct 11 ms 15180 KB Output is correct
18 Correct 11 ms 15180 KB Output is correct
19 Correct 289 ms 25156 KB Output is correct
20 Correct 290 ms 25156 KB Output is correct
21 Correct 313 ms 25404 KB Output is correct
22 Correct 272 ms 25224 KB Output is correct
23 Correct 474 ms 26364 KB Output is correct
24 Correct 305 ms 24908 KB Output is correct
25 Incorrect 146 ms 39364 KB Output isn't correct
26 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 15180 KB Output is correct
2 Correct 11 ms 15176 KB Output is correct
3 Correct 10 ms 15180 KB Output is correct
4 Correct 11 ms 15252 KB Output is correct
5 Correct 10 ms 15168 KB Output is correct
6 Correct 11 ms 15256 KB Output is correct
7 Correct 11 ms 15180 KB Output is correct
8 Correct 11 ms 15272 KB Output is correct
9 Correct 11 ms 15196 KB Output is correct
10 Correct 11 ms 15180 KB Output is correct
11 Correct 10 ms 15180 KB Output is correct
12 Correct 12 ms 15276 KB Output is correct
13 Correct 11 ms 15180 KB Output is correct
14 Correct 12 ms 15184 KB Output is correct
15 Correct 11 ms 15152 KB Output is correct
16 Correct 12 ms 15188 KB Output is correct
17 Correct 11 ms 15180 KB Output is correct
18 Correct 11 ms 15180 KB Output is correct
19 Correct 11 ms 15180 KB Output is correct
20 Correct 11 ms 15212 KB Output is correct
21 Correct 12 ms 15436 KB Output is correct
22 Correct 14 ms 15700 KB Output is correct
23 Correct 13 ms 15672 KB Output is correct
24 Correct 13 ms 15564 KB Output is correct
25 Correct 13 ms 15692 KB Output is correct
26 Correct 14 ms 15692 KB Output is correct
27 Correct 11 ms 15336 KB Output is correct
28 Correct 13 ms 15692 KB Output is correct
29 Correct 13 ms 15692 KB Output is correct
30 Correct 14 ms 15692 KB Output is correct
31 Correct 14 ms 15692 KB Output is correct
32 Correct 13 ms 15692 KB Output is correct
33 Correct 14 ms 15680 KB Output is correct
34 Correct 13 ms 15564 KB Output is correct
35 Correct 12 ms 15588 KB Output is correct
36 Correct 12 ms 15564 KB Output is correct
37 Correct 12 ms 15564 KB Output is correct
38 Correct 13 ms 15604 KB Output is correct
39 Correct 289 ms 25156 KB Output is correct
40 Correct 290 ms 25156 KB Output is correct
41 Correct 313 ms 25404 KB Output is correct
42 Correct 272 ms 25224 KB Output is correct
43 Correct 474 ms 26364 KB Output is correct
44 Correct 305 ms 24908 KB Output is correct
45 Incorrect 146 ms 39364 KB Output isn't correct
46 Halted 0 ms 0 KB -