oj.uz

Submission #1083479

# Submission time Handle Problem Language Result Execution time Memory
1083479 2024-09-03T09:28:14 Z Namviet2704 Race (IOI11_race) C++17
9 / 100
 455 ms 14336 KB 
#include <bits/stdc++.h>
//#include "race.h"
#define ll long long
#define fi first
#define se second
#define pii pair<int, int>

using namespace std;

const int N = 2e5 + 5;

int n, k, ans = 1e9;
vector<pii> vt[N];
int in[N], out[N], pos[N], sz[N], kq[N];
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;
        dfs(v.fi, u);
        sz[u] += sz[v.fi];
    }
    out[u] = cnt;
}

map<ll, pii> mp;

void add(int u)
{
    for(int i = in[u]; i <= out[u]; i++)
    {
        if(mp[h[pos[i]].fi].fi == 0)
            mp[h[pos[i]].fi] = {h[pos[i]].se, pos[i]};
        else
            mp[h[pos[i]].fi] = min(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)
            add(v.fi);
    mp[h[u].fi] = {h[u].se, u};
    for(int i = in[u]; i <= out[u]; i++)
    {
        if(big.se != -1 && in[big.se] <= i && i <= out[big.se])
            continue;
        int v = pos[i];
        ll tmp = h[u].fi + k - (h[v].fi - h[u].fi);
//        cout << u << " " << v << " " << tmp << " " << mp[tmp].fi << '\n';
        if(mp[tmp].fi == 0)
            continue;
        int haha = mp[tmp].se;
        if(out[haha] < in[v] || out[v] < in[haha] || v == u)
            ans = min(ans, h[haha].se - h[u].se + h[v].se - 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 4956 KB Output is correct
2 Correct 3 ms 5140 KB Output is correct
3 Correct 2 ms 4956 KB Output is correct
4 Correct 2 ms 4956 KB Output is correct
5 Correct 4 ms 4956 KB Output is correct
6 Correct 3 ms 4956 KB Output is correct
7 Correct 3 ms 4956 KB Output is correct
8 Correct 3 ms 5212 KB Output is correct
9 Correct 2 ms 4952 KB Output is correct
10 Correct 2 ms 5128 KB Output is correct
11 Correct 2 ms 4956 KB Output is correct
12 Correct 3 ms 4956 KB Output is correct
13 Correct 2 ms 4956 KB Output is correct
14 Correct 2 ms 4956 KB Output is correct
15 Correct 2 ms 4956 KB Output is correct
16 Correct 2 ms 4956 KB Output is correct
17 Correct 3 ms 5096 KB Output is correct
18 Correct 3 ms 5120 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4956 KB Output is correct
2 Correct 3 ms 5140 KB Output is correct
3 Correct 2 ms 4956 KB Output is correct
4 Correct 2 ms 4956 KB Output is correct
5 Correct 4 ms 4956 KB Output is correct
6 Correct 3 ms 4956 KB Output is correct
7 Correct 3 ms 4956 KB Output is correct
8 Correct 3 ms 5212 KB Output is correct
9 Correct 2 ms 4952 KB Output is correct
10 Correct 2 ms 5128 KB Output is correct
11 Correct 2 ms 4956 KB Output is correct
12 Correct 3 ms 4956 KB Output is correct
13 Correct 2 ms 4956 KB Output is correct
14 Correct 2 ms 4956 KB Output is correct
15 Correct 2 ms 4956 KB Output is correct
16 Correct 2 ms 4956 KB Output is correct
17 Correct 3 ms 5096 KB Output is correct
18 Correct 3 ms 5120 KB Output is correct
19 Correct 3 ms 4956 KB Output is correct
20 Correct 3 ms 4956 KB Output is correct
21 Correct 6 ms 5300 KB Output is correct
22 Correct 7 ms 5464 KB Output is correct
23 Correct 9 ms 5468 KB Output is correct
24 Correct 8 ms 5468 KB Output is correct
25 Correct 8 ms 5468 KB Output is correct
26 Incorrect 10 ms 5496 KB Output isn't correct
27 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4956 KB Output is correct
2 Correct 3 ms 5140 KB Output is correct
3 Correct 2 ms 4956 KB Output is correct
4 Correct 2 ms 4956 KB Output is correct
5 Correct 4 ms 4956 KB Output is correct
6 Correct 3 ms 4956 KB Output is correct
7 Correct 3 ms 4956 KB Output is correct
8 Correct 3 ms 5212 KB Output is correct
9 Correct 2 ms 4952 KB Output is correct
10 Correct 2 ms 5128 KB Output is correct
11 Correct 2 ms 4956 KB Output is correct
12 Correct 3 ms 4956 KB Output is correct
13 Correct 2 ms 4956 KB Output is correct
14 Correct 2 ms 4956 KB Output is correct
15 Correct 2 ms 4956 KB Output is correct
16 Correct 2 ms 4956 KB Output is correct
17 Correct 3 ms 5096 KB Output is correct
18 Correct 3 ms 5120 KB Output is correct
19 Incorrect 455 ms 14336 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4956 KB Output is correct
2 Correct 3 ms 5140 KB Output is correct
3 Correct 2 ms 4956 KB Output is correct
4 Correct 2 ms 4956 KB Output is correct
5 Correct 4 ms 4956 KB Output is correct
6 Correct 3 ms 4956 KB Output is correct
7 Correct 3 ms 4956 KB Output is correct
8 Correct 3 ms 5212 KB Output is correct
9 Correct 2 ms 4952 KB Output is correct
10 Correct 2 ms 5128 KB Output is correct
11 Correct 2 ms 4956 KB Output is correct
12 Correct 3 ms 4956 KB Output is correct
13 Correct 2 ms 4956 KB Output is correct
14 Correct 2 ms 4956 KB Output is correct
15 Correct 2 ms 4956 KB Output is correct
16 Correct 2 ms 4956 KB Output is correct
17 Correct 3 ms 5096 KB Output is correct
18 Correct 3 ms 5120 KB Output is correct
19 Correct 3 ms 4956 KB Output is correct
20 Correct 3 ms 4956 KB Output is correct
21 Correct 6 ms 5300 KB Output is correct
22 Correct 7 ms 5464 KB Output is correct
23 Correct 9 ms 5468 KB Output is correct
24 Correct 8 ms 5468 KB Output is correct
25 Correct 8 ms 5468 KB Output is correct
26 Incorrect 10 ms 5496 KB Output isn't correct
27 Halted 0 ms 0 KB -