oj.uz

Submission #1104235

# Submission time Handle Problem Language Result Execution time Memory
1104235 2024-10-23T09:44:54 Z LonlyR Race (IOI11_race) C++17
0 / 100
 6 ms 35152 KB 
#include<bits/stdc++.h>

using namespace std;
const int maxn = 1e6 + 5;
int n, k, ans = -1;
int sz[maxn], mark[maxn], cnt[maxn];
vector<pair<int,int>> adj[maxn];

void get_size(int x, int p)
{
    sz[x] = 1;
    for (auto [i, j] : adj[x]) if (i != p && !mark[i])
        get_size(i, x),
        sz[x] += sz[i];
}

int find(int x, int p, int half)
{
    for (auto [i, j] : adj[x]) if (i != p && !mark[i] && sz[i] > half)
        return find(i, x, half);
    return x;
}

void dfs(int x, int p, int h, int d, int t)
{
    if (h > k) return;
    if (t == 0)
    {
        if (cnt[k - h] != -1)
        {
            if (ans == -1)
                ans = d + cnt[k - h];
            else ans = min(ans, d + cnt[k - h]);
        }
    } else if (cnt[h] == -1) cnt[h] = d; else cnt[h] = min(cnt[h], d);
    for (auto [i, j] : adj[x]) if (i != p)
        dfs(i, x, h + j, d + 1, t);
}

void reset(int x, int p, int h)
{
    if (h > k) return;
    cnt[h] = -1;
    for (auto [i, j] : adj[x])if (i != p && !mark[i])
        reset(i, x, h + j);
}

void solve(int x = 1)
{
    get_size(x, x);
    x = find(x, x, sz[x] / 2);
    mark[x] = 1;
    cnt[0] = 0;
    for (auto [i, j] : adj[x]) if (!mark[i])
        dfs(i, x, j, 1, 1),
        dfs(i, x, j, 1, 0);
    reset(x, x, 0);
    for (auto [i, j] : adj[x]) if (!mark[i])
        solve(i);
}

int best_path(int N, int K, int H[][2], int L[])
{
    n = N, k = K;
    memset(cnt, -1, sizeof cnt);
    for(int i = 0; i < n - 1; i++){
        int u = H[i][0] + 1, v = H[i][1] + 1, w = L[i];
        adj[u].emplace_back(v, w);
        adj[v].emplace_back(u, w);
    }
    solve();
    return ans;
}

//signed main()
//{
//    ios_base::sync_with_stdio(false);
//    cin.tie(0); cout.tie(0);
////    freopen("test.inp", "r", stdin);
////    freopen("test.out", "w", stdout);
//    cin >> n >> k;
//    for(int i = 0; i < n - 1; i++){
//        int u, v, w; cin >> u >> v >> w;
//        u++; v++;
//        adj[u].emplace_back(v, w);
//        adj[v].emplace_back(u, w);
//    }
//    memset(cnt, -1, sizeof cnt);
//    solve();
//    cout << ans;
//}

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 35152 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 35152 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 35152 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 35152 KB Output isn't correct
2 Halted 0 ms 0 KB -