oj.uz

Submission #405095

# Submission time Handle Problem Language Result Execution time Memory
405095 2021-05-15T17:12:39 Z Vladth11 Race (IOI11_race) C++14
100 / 100
 1447 ms 72852 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define debug(x) cerr << #x << " " << x << "\n"
#define debug_with_space(x) cerr << #x << " " << x << " "
#include"race.h"
 
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef pair <ll, ll> pii;
typedef pair <long double, pii> muchie;
typedef tree <ll, null_type, less_equal <ll>, rb_tree_tag, tree_order_statistics_node_update> OST;
 
const ll NMAX = 200001;
const ll INF = (1LL << 60);
const ll MOD = 1000000009;
const ll BLOCK = 225;
const ll base = 31;
const ll base2 = 53;
const ll nr_of_bits = 21;
 
vector <pii> v[NMAX];
int best = 2e9;
int k;
int sz[NMAX];
int total;
int viz[NMAX];
int d[NMAX];
vector <pii> mp[1000001];
 
void getsize(int node, int p){
    sz[node] = 1;
    for(auto x : v[node]){
        if(x.first == p || viz[x.first])
            continue;
        getsize(x.first, node);
        sz[node] += sz[x.first];
    }
  total = sz[node];
}
 
int centroid(int node, int p){
    for(auto x : v[node]){
        if(viz[x.first] || x.first == p){
            continue;
        }
        if(sz[x.first] > total / 2)
            return centroid(x.first, node);
    }
    return node;
}
 
int OneCentroid(int node){
    getsize(node, 0);
    return centroid(node, 0);
}
 
 
void ComputeDist(int node, int p, int subTree, int dist, int level){
    d[node] = dist;
    pii act = {level, subTree};
    if(dist <= k && (!mp[dist].size() || mp[dist].back().first >= level))
        mp[dist].push_back(act);
    for(auto x : v[node]){
        if(x.first == p || viz[x.first])
            continue;
        ComputeDist(x.first, node, subTree, d[node] + x.second, level + 1);
    }
}
 
 
void SuperErase(int node, int p, int subTree, int level){
    int dist = d[node];
    pii act = {level, subTree};
    if(dist <= k){
       mp[dist].clear();
    }
    for(auto x : v[node]){
        if(x.first == p || viz[x.first])
            continue;
        SuperErase(x.first, node, subTree, level + 1);
    }
}
 
void Erase(int node, int p, int subTree, int level){
    int dist = d[node];
    pii act = {level, subTree};
    if(dist <= k && (mp[dist].size() && mp[dist].back() == act))
        mp[dist].pop_back();
    for(auto x : v[node]){
        if(x.first == p || viz[x.first])
            continue;
        Erase(x.first, node, subTree, level + 1);
    }
}
 
void Add(int node, int p, int subTree, int level){
    int dist = d[node];
    pii act = {level, subTree};
    if(dist <= k && (!mp[dist].size() ||mp[dist].back().first >= level))
        mp[dist].push_back(act);
    for(auto x : v[node]){
        if(x.first == p || viz[x.first])
            continue;
        Add(x.first, node, subTree, level + 1);
    }
}
 
void Compute(int node, int p, int level){
    int trb = k - d[node];
    if(trb >= 0 && mp[trb].size() != 0)
    {
        int b = mp[trb].back().first;
        best = min(best, b + level);
    }
    for(auto x : v[node]){
        if(x.first == p || viz[x.first])
            continue;
        Compute(x.first, node, level + 1);
    }
}
 
 
void CD(int node){
    int c = OneCentroid(node);
    viz[c] = 1;
    mp[0].push_back({0, 0});
    for(auto x : v[c]){
        if(viz[x.first])
            continue;
        ComputeDist(x.first, c, x.first, x.second, 1);
    }
    for(auto x : v[c]){
        if(viz[x.first])
            continue;
        Erase(x.first, c, x.first, 1);
        Compute(x.first, 0, 1);
        Add(x.first, c, x.first, 1);
    }
      for(auto x : v[c]){
        if(viz[x.first])
            continue;
        SuperErase(x.first, c, x.first, 1);
    }
 
     for(auto x : v[c]){
        if(viz[x.first])
            continue;
        CD(x.first);
    }
}
 
int best_path(int N, int K, int H[][2], int L[])
{
    k = K;
    for(int i = 0; i < N - 1; i++){
        int a = H[i][0] + 1;
        int b = H[i][1] + 1;
        v[a].push_back({b, L[i]});
        v[b].push_back({a, L[i]});
    }
   for(int i = 0; i <= k; i++)
       mp[i].clear();
    CD(1);
    if(best == 2e9)
        best = -1;
    return best;
}

Compilation message

race.cpp: In function 'void SuperErase(int, int, int, int)':
race.cpp:75:9: warning: variable 'act' set but not used [-Wunused-but-set-variable]
   75 |     pii act = {level, subTree};
      |         ^~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 28436 KB Output is correct
2 Correct 16 ms 28412 KB Output is correct
3 Correct 16 ms 28404 KB Output is correct
4 Correct 18 ms 28516 KB Output is correct
5 Correct 16 ms 28492 KB Output is correct
6 Correct 17 ms 28504 KB Output is correct
7 Correct 17 ms 28524 KB Output is correct
8 Correct 18 ms 28408 KB Output is correct
9 Correct 18 ms 28492 KB Output is correct
10 Correct 16 ms 28428 KB Output is correct
11 Correct 16 ms 28524 KB Output is correct
12 Correct 19 ms 28492 KB Output is correct
13 Correct 17 ms 28464 KB Output is correct
14 Correct 17 ms 28484 KB Output is correct
15 Correct 16 ms 28492 KB Output is correct
16 Correct 16 ms 28492 KB Output is correct
17 Correct 16 ms 28500 KB Output is correct
18 Correct 16 ms 28492 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 28436 KB Output is correct
2 Correct 16 ms 28412 KB Output is correct
3 Correct 16 ms 28404 KB Output is correct
4 Correct 18 ms 28516 KB Output is correct
5 Correct 16 ms 28492 KB Output is correct
6 Correct 17 ms 28504 KB Output is correct
7 Correct 17 ms 28524 KB Output is correct
8 Correct 18 ms 28408 KB Output is correct
9 Correct 18 ms 28492 KB Output is correct
10 Correct 16 ms 28428 KB Output is correct
11 Correct 16 ms 28524 KB Output is correct
12 Correct 19 ms 28492 KB Output is correct
13 Correct 17 ms 28464 KB Output is correct
14 Correct 17 ms 28484 KB Output is correct
15 Correct 16 ms 28492 KB Output is correct
16 Correct 16 ms 28492 KB Output is correct
17 Correct 16 ms 28500 KB Output is correct
18 Correct 16 ms 28492 KB Output is correct
19 Correct 16 ms 28492 KB Output is correct
20 Correct 17 ms 28444 KB Output is correct
21 Correct 18 ms 28572 KB Output is correct
22 Correct 21 ms 28564 KB Output is correct
23 Correct 21 ms 28544 KB Output is correct
24 Correct 20 ms 28560 KB Output is correct
25 Correct 20 ms 28620 KB Output is correct
26 Correct 18 ms 28620 KB Output is correct
27 Correct 19 ms 28528 KB Output is correct
28 Correct 18 ms 28620 KB Output is correct
29 Correct 19 ms 28616 KB Output is correct
30 Correct 19 ms 28748 KB Output is correct
31 Correct 21 ms 28632 KB Output is correct
32 Correct 21 ms 28748 KB Output is correct
33 Correct 21 ms 28748 KB Output is correct
34 Correct 19 ms 28620 KB Output is correct
35 Correct 25 ms 28748 KB Output is correct
36 Correct 24 ms 28620 KB Output is correct
37 Correct 21 ms 28768 KB Output is correct
38 Correct 19 ms 28748 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 28436 KB Output is correct
2 Correct 16 ms 28412 KB Output is correct
3 Correct 16 ms 28404 KB Output is correct
4 Correct 18 ms 28516 KB Output is correct
5 Correct 16 ms 28492 KB Output is correct
6 Correct 17 ms 28504 KB Output is correct
7 Correct 17 ms 28524 KB Output is correct
8 Correct 18 ms 28408 KB Output is correct
9 Correct 18 ms 28492 KB Output is correct
10 Correct 16 ms 28428 KB Output is correct
11 Correct 16 ms 28524 KB Output is correct
12 Correct 19 ms 28492 KB Output is correct
13 Correct 17 ms 28464 KB Output is correct
14 Correct 17 ms 28484 KB Output is correct
15 Correct 16 ms 28492 KB Output is correct
16 Correct 16 ms 28492 KB Output is correct
17 Correct 16 ms 28500 KB Output is correct
18 Correct 16 ms 28492 KB Output is correct
19 Correct 328 ms 38228 KB Output is correct
20 Correct 359 ms 38144 KB Output is correct
21 Correct 351 ms 38112 KB Output is correct
22 Correct 395 ms 38164 KB Output is correct
23 Correct 211 ms 38472 KB Output is correct
24 Correct 131 ms 37696 KB Output is correct
25 Correct 314 ms 40972 KB Output is correct
26 Correct 162 ms 43332 KB Output is correct
27 Correct 325 ms 48088 KB Output is correct
28 Correct 881 ms 62388 KB Output is correct
29 Correct 951 ms 61144 KB Output is correct
30 Correct 311 ms 48152 KB Output is correct
31 Correct 344 ms 48216 KB Output is correct
32 Correct 428 ms 48188 KB Output is correct
33 Correct 599 ms 47016 KB Output is correct
34 Correct 628 ms 46932 KB Output is correct

Subtask #4
57.0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 28436 KB Output is correct
2 Correct 16 ms 28412 KB Output is correct
3 Correct 16 ms 28404 KB Output is correct
4 Correct 18 ms 28516 KB Output is correct
5 Correct 16 ms 28492 KB Output is correct
6 Correct 17 ms 28504 KB Output is correct
7 Correct 17 ms 28524 KB Output is correct
8 Correct 18 ms 28408 KB Output is correct
9 Correct 18 ms 28492 KB Output is correct
10 Correct 16 ms 28428 KB Output is correct
11 Correct 16 ms 28524 KB Output is correct
12 Correct 19 ms 28492 KB Output is correct
13 Correct 17 ms 28464 KB Output is correct
14 Correct 17 ms 28484 KB Output is correct
15 Correct 16 ms 28492 KB Output is correct
16 Correct 16 ms 28492 KB Output is correct
17 Correct 16 ms 28500 KB Output is correct
18 Correct 16 ms 28492 KB Output is correct
19 Correct 16 ms 28492 KB Output is correct
20 Correct 17 ms 28444 KB Output is correct
21 Correct 18 ms 28572 KB Output is correct
22 Correct 21 ms 28564 KB Output is correct
23 Correct 21 ms 28544 KB Output is correct
24 Correct 20 ms 28560 KB Output is correct
25 Correct 20 ms 28620 KB Output is correct
26 Correct 18 ms 28620 KB Output is correct
27 Correct 19 ms 28528 KB Output is correct
28 Correct 18 ms 28620 KB Output is correct
29 Correct 19 ms 28616 KB Output is correct
30 Correct 19 ms 28748 KB Output is correct
31 Correct 21 ms 28632 KB Output is correct
32 Correct 21 ms 28748 KB Output is correct
33 Correct 21 ms 28748 KB Output is correct
34 Correct 19 ms 28620 KB Output is correct
35 Correct 25 ms 28748 KB Output is correct
36 Correct 24 ms 28620 KB Output is correct
37 Correct 21 ms 28768 KB Output is correct
38 Correct 19 ms 28748 KB Output is correct
39 Correct 328 ms 38228 KB Output is correct
40 Correct 359 ms 38144 KB Output is correct
41 Correct 351 ms 38112 KB Output is correct
42 Correct 395 ms 38164 KB Output is correct
43 Correct 211 ms 38472 KB Output is correct
44 Correct 131 ms 37696 KB Output is correct
45 Correct 314 ms 40972 KB Output is correct
46 Correct 162 ms 43332 KB Output is correct
47 Correct 325 ms 48088 KB Output is correct
48 Correct 881 ms 62388 KB Output is correct
49 Correct 951 ms 61144 KB Output is correct
50 Correct 311 ms 48152 KB Output is correct
51 Correct 344 ms 48216 KB Output is correct
52 Correct 428 ms 48188 KB Output is correct
53 Correct 599 ms 47016 KB Output is correct
54 Correct 628 ms 46932 KB Output is correct
55 Correct 32 ms 29812 KB Output is correct
56 Correct 34 ms 29632 KB Output is correct
57 Correct 163 ms 38388 KB Output is correct
58 Correct 63 ms 42652 KB Output is correct
59 Correct 217 ms 48788 KB Output is correct
60 Correct 1236 ms 72852 KB Output is correct
61 Correct 344 ms 48580 KB Output is correct
62 Correct 349 ms 49240 KB Output is correct
63 Correct 482 ms 49464 KB Output is correct
64 Correct 1447 ms 56628 KB Output is correct
65 Correct 752 ms 47636 KB Output is correct
66 Correct 1295 ms 62596 KB Output is correct
67 Correct 188 ms 57500 KB Output is correct
68 Correct 622 ms 53936 KB Output is correct
69 Correct 608 ms 53776 KB Output is correct
70 Correct 612 ms 53080 KB Output is correct