oj.uz

Submission #1083604

# Submission time Handle Problem Language Result Execution time Memory
1083604 2024-09-03T14:52:30 Z Namviet2704 Race (IOI11_race) C++17
100 / 100
 1269 ms 138508 KB 
#include <bits/stdc++.h>
//#include "race.h"
#define task "road"
#define ll long long
#define fi first
#define se second
#define pii pair<ll, ll>

using namespace std;

const int N = 2e5 + 5;

ll n, k, ans = 1e9;
vector<pii> vt[N];
ll in[N], out[N], pos[N], sz[N], up[N][22];
pair<ll, int> h[N];
int cnt = 0;

void dfs(int u, int p)
{
    in[u] = ++cnt;
    pos[cnt] = u;
    sz[u] = 1;
    for(auto v : vt[u])
    {
        if(v.fi == p)
            continue;
        h[v.fi].fi = h[u].fi + v.se;
        h[v.fi].se = h[u].se + 1;
        up[v.fi][0] = u;
        for(int i = 1; i <= 20; i++)
            up[v.fi][i] = up[up[v.fi][i - 1]][i - 1];
        dfs(v.fi, u);
        sz[u] += sz[v.fi];
    }
    out[u] = cnt;
}

int lca(int u, int v)
{
    if(h[u].se != h[v].se)
    {
        if(h[u].se < h[v].se)
            swap(u, v);
        int tmp = h[u].se - h[v].se;
        for(int i = 0; i <= 20; i++)
            if((tmp >> i) & 1)
                u = up[u][i];
    }
    if(u == v)
        return u;
    for(int i = 20; i >= 0; i--)
        if(up[u][i] != up[v][i])
        {
            u = up[u][i];
            v = up[v][i];
        }
    return up[u][0];
}

map<ll, pii> mp;

void add(int u)
{
    for(int i = in[u]; i <= out[u]; i++)
    {
        pii tmp = mp[h[pos[i]].fi];
        if(tmp.fi == 0 || tmp.fi > h[pos[i]].se)
            mp[h[pos[i]].fi] = {h[pos[i]].se, pos[i]};
    }
}

void del(int u)
{
    for(int i = in[u]; i <= out[u]; i++)
        mp[h[pos[i]].fi] = {0, 0};
}

void solve(int u, int p)
{
    pair<int, int> big = {0, -1};
    for(auto v : vt[u])
        if(v.fi != p)
            big = max(big, {sz[v.fi], v.fi});
    for(auto v : vt[u])
    {
        if(v.fi == big.se || v.fi == p)
            continue;
        solve(v.fi, u);
        del(v.fi);
    }
    if(big.se != -1)
        solve(big.se, u);
    for(auto v : vt[u])
        if(v.fi != big.se && v.fi != p)
            add(v.fi);
    mp[h[u].fi] = {h[u].se, u};
    for(auto j : vt[u])
    {
        if(j.fi != big.se && j.fi != p)
            for(int i = in[j.fi]; i <= out[j.fi]; i++)
            {
                int v = pos[i];
                ll tmp = h[u].fi + k - (h[v].fi - h[u].fi);
                pii huhu = mp[tmp];
                if(huhu.fi == 0)
                    continue;
                int haha = huhu.se;
                if(lca(haha, v) == u)
                    ans = min(ans, huhu.fi - h[u].se + h[v].se - h[u].se);
//                if(ans == 4)
//                    cout << u << " " << v << " " << haha << '\n';
            }
    }
    pii huhu = mp[h[u].fi + k];
    if(huhu.fi == 0)
        return;
    ans = min(ans, huhu.fi - h[u].se);
    return;
}

int best_path(int m, int g, int h[][2], int l[])
{
    n = m;
    k = g;
    for(int i = 0; i < n - 1; i++)
    {
        vt[h[i][0]].push_back({h[i][1], l[i]});
        vt[h[i][1]].push_back({h[i][0], l[i]});
    }
    dfs(0, -1);
    solve(0, -1);
    if(ans == (int) 1e9)
        return -1;
    return ans;
}

//int main()
//{
//    freopen(task".inp", "r", stdin);
//    freopen(task".out", "w", stdout);
//    ios_base::sync_with_stdio(false);
//    cin.tie(NULL), cout.tie(NULL);
//    cin >> n >> k;
//    for(int i = 1; i < n; i++)
//    {
//        int x, y, w;
//        cin >> x >> y >> w;
//        vt[x].push_back({y, w});
//        vt[y].push_back({x, w});
//    }
//    dfs(0, -1);
//    cout << best_path();
//    return 0;
//}

/*
4 3
0 1 1
1 2 2
1 3 4
11 12
0 1 3
0 2 4
2 3 5
3 4 4
4 5 6
0 6 3
6 7 2
6 8 5
8 9 6
8 10 7
*/

Subtask #1
9.0 / 9.0

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

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5212 KB Output is correct
2 Correct 3 ms 5212 KB Output is correct
3 Correct 2 ms 5208 KB Output is correct
4 Correct 2 ms 5212 KB Output is correct
5 Correct 3 ms 5212 KB Output is correct
6 Correct 3 ms 5212 KB Output is correct
7 Correct 3 ms 5140 KB Output is correct
8 Correct 2 ms 5212 KB Output is correct
9 Correct 2 ms 5212 KB Output is correct
10 Correct 2 ms 5212 KB Output is correct
11 Correct 2 ms 5212 KB Output is correct
12 Correct 3 ms 5212 KB Output is correct
13 Correct 2 ms 5212 KB Output is correct
14 Correct 2 ms 5212 KB Output is correct
15 Correct 2 ms 5212 KB Output is correct
16 Correct 2 ms 5212 KB Output is correct
17 Correct 2 ms 5212 KB Output is correct
18 Correct 2 ms 5212 KB Output is correct
19 Correct 2 ms 4956 KB Output is correct
20 Correct 2 ms 5212 KB Output is correct
21 Correct 3 ms 5468 KB Output is correct
22 Correct 4 ms 5724 KB Output is correct
23 Correct 3 ms 5720 KB Output is correct
24 Correct 5 ms 5592 KB Output is correct
25 Correct 6 ms 5508 KB Output is correct
26 Correct 4 ms 5724 KB Output is correct
27 Correct 3 ms 5488 KB Output is correct
28 Correct 3 ms 5720 KB Output is correct
29 Correct 4 ms 5724 KB Output is correct
30 Correct 3 ms 5724 KB Output is correct
31 Correct 3 ms 5724 KB Output is correct
32 Correct 3 ms 5664 KB Output is correct
33 Correct 4 ms 5720 KB Output is correct
34 Correct 3 ms 5468 KB Output is correct
35 Correct 4 ms 5468 KB Output is correct
36 Correct 3 ms 5468 KB Output is correct
37 Correct 3 ms 5468 KB Output is correct
38 Correct 3 ms 5468 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5212 KB Output is correct
2 Correct 3 ms 5212 KB Output is correct
3 Correct 2 ms 5208 KB Output is correct
4 Correct 2 ms 5212 KB Output is correct
5 Correct 3 ms 5212 KB Output is correct
6 Correct 3 ms 5212 KB Output is correct
7 Correct 3 ms 5140 KB Output is correct
8 Correct 2 ms 5212 KB Output is correct
9 Correct 2 ms 5212 KB Output is correct
10 Correct 2 ms 5212 KB Output is correct
11 Correct 2 ms 5212 KB Output is correct
12 Correct 3 ms 5212 KB Output is correct
13 Correct 2 ms 5212 KB Output is correct
14 Correct 2 ms 5212 KB Output is correct
15 Correct 2 ms 5212 KB Output is correct
16 Correct 2 ms 5212 KB Output is correct
17 Correct 2 ms 5212 KB Output is correct
18 Correct 2 ms 5212 KB Output is correct
19 Correct 140 ms 34668 KB Output is correct
20 Correct 139 ms 34640 KB Output is correct
21 Correct 173 ms 34640 KB Output is correct
22 Correct 139 ms 34768 KB Output is correct
23 Correct 184 ms 35152 KB Output is correct
24 Correct 131 ms 34404 KB Output is correct
25 Correct 121 ms 44040 KB Output is correct
26 Correct 85 ms 51540 KB Output is correct
27 Correct 187 ms 65108 KB Output is correct
28 Correct 247 ms 122964 KB Output is correct
29 Correct 233 ms 121228 KB Output is correct
30 Correct 157 ms 65104 KB Output is correct
31 Correct 159 ms 65108 KB Output is correct
32 Correct 210 ms 65364 KB Output is correct
33 Correct 202 ms 64080 KB Output is correct
34 Correct 743 ms 121260 KB Output is correct

Subtask #4
57.0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5212 KB Output is correct
2 Correct 3 ms 5212 KB Output is correct
3 Correct 2 ms 5208 KB Output is correct
4 Correct 2 ms 5212 KB Output is correct
5 Correct 3 ms 5212 KB Output is correct
6 Correct 3 ms 5212 KB Output is correct
7 Correct 3 ms 5140 KB Output is correct
8 Correct 2 ms 5212 KB Output is correct
9 Correct 2 ms 5212 KB Output is correct
10 Correct 2 ms 5212 KB Output is correct
11 Correct 2 ms 5212 KB Output is correct
12 Correct 3 ms 5212 KB Output is correct
13 Correct 2 ms 5212 KB Output is correct
14 Correct 2 ms 5212 KB Output is correct
15 Correct 2 ms 5212 KB Output is correct
16 Correct 2 ms 5212 KB Output is correct
17 Correct 2 ms 5212 KB Output is correct
18 Correct 2 ms 5212 KB Output is correct
19 Correct 2 ms 4956 KB Output is correct
20 Correct 2 ms 5212 KB Output is correct
21 Correct 3 ms 5468 KB Output is correct
22 Correct 4 ms 5724 KB Output is correct
23 Correct 3 ms 5720 KB Output is correct
24 Correct 5 ms 5592 KB Output is correct
25 Correct 6 ms 5508 KB Output is correct
26 Correct 4 ms 5724 KB Output is correct
27 Correct 3 ms 5488 KB Output is correct
28 Correct 3 ms 5720 KB Output is correct
29 Correct 4 ms 5724 KB Output is correct
30 Correct 3 ms 5724 KB Output is correct
31 Correct 3 ms 5724 KB Output is correct
32 Correct 3 ms 5664 KB Output is correct
33 Correct 4 ms 5720 KB Output is correct
34 Correct 3 ms 5468 KB Output is correct
35 Correct 4 ms 5468 KB Output is correct
36 Correct 3 ms 5468 KB Output is correct
37 Correct 3 ms 5468 KB Output is correct
38 Correct 3 ms 5468 KB Output is correct
39 Correct 140 ms 34668 KB Output is correct
40 Correct 139 ms 34640 KB Output is correct
41 Correct 173 ms 34640 KB Output is correct
42 Correct 139 ms 34768 KB Output is correct
43 Correct 184 ms 35152 KB Output is correct
44 Correct 131 ms 34404 KB Output is correct
45 Correct 121 ms 44040 KB Output is correct
46 Correct 85 ms 51540 KB Output is correct
47 Correct 187 ms 65108 KB Output is correct
48 Correct 247 ms 122964 KB Output is correct
49 Correct 233 ms 121228 KB Output is correct
50 Correct 157 ms 65104 KB Output is correct
51 Correct 159 ms 65108 KB Output is correct
52 Correct 210 ms 65364 KB Output is correct
53 Correct 202 ms 64080 KB Output is correct
54 Correct 743 ms 121260 KB Output is correct
55 Correct 18 ms 8796 KB Output is correct
56 Correct 10 ms 8028 KB Output is correct
57 Correct 86 ms 34836 KB Output is correct
58 Correct 51 ms 33836 KB Output is correct
59 Correct 89 ms 63616 KB Output is correct
60 Correct 276 ms 121348 KB Output is correct
61 Correct 227 ms 68688 KB Output is correct
62 Correct 145 ms 65360 KB Output is correct
63 Correct 248 ms 65620 KB Output is correct
64 Correct 1029 ms 92780 KB Output is correct
65 Correct 1269 ms 138508 KB Output is correct
66 Correct 254 ms 117888 KB Output is correct
67 Correct 153 ms 64180 KB Output is correct
68 Correct 581 ms 100864 KB Output is correct
69 Correct 573 ms 101428 KB Output is correct
70 Correct 575 ms 96472 KB Output is correct