oj.uz

Submission #971549

# Submission time Handle Problem Language Result Execution time Memory
971549 2024-04-28T20:53:08 Z vladilius Race (IOI11_race) C++17
0 / 100
 3 ms 8796 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
const int msz = 2e5 + 5;
const int lg = 25;

struct edge{
    int to, t;
    edge(int a, int b){
        to = a; t = b;
    }
};

vector<edge> g[msz];
vector<int> cl[lg], out, sz;

void fill(int v, int pr){
    sz[v] = 1;
    for (auto i: g[v]){
        if (i.to == pr || out[i.to]) continue;
        fill(i.to, v);
        sz[v] += sz[i.to];
    }
}

int find(int v, int pr, int& x){
    for (auto i: g[v]){
        if (i.to == pr || out[i.to]) continue;
        if (2 * sz[i.to] >= x) return find(i.to, v, x);
    }
    return v;
}

void build(int v, int cnt){
    fill(v, 0);
    int u = find(v, 0, sz[v]);
    out[u] = cnt++;
    cl[out[u]].push_back(u);
    for (auto i: g[u]){
        if (out[i.to]) continue;
        build(i.to, cnt);
    }
}

vector<ll> weight;
vector<pair<int, int>> p;
vector<bool> used;

void fill_dfs(int v, int pr){
    for (auto i: g[v]){
        if (i.to == pr || used[i.to]) continue;
        weight[i.to] = weight[v] + i.t;
        fill_dfs(i.to, v);
    }
}

void add(int v, int pr, int cnt){
    p.push_back({v, cnt++});
    for (auto i: g[v]){
        if (i.to == pr || used[i.to]) continue;
        add(i.to, v, cnt);
    }
}

int ans = msz, l;

void solve(int v, int cnt){
    weight[v] = 0;
    used[v] = true;
    fill_dfs(v, 0);
    map<ll, int> mp;
    for (auto i: g[v]){
        if (used[i.to]) continue;
        add(i.to, 0, 1);
        for (auto j: p){
            if (weight[j.first] > l) continue;
            if (weight[j.first] == l){
                ans = min(ans, j.second);
                continue;
            }
            int x = mp[l - weight[j.first]];
            if (x > 0) ans = min(ans, j.second + x);
        }
        for (auto j: p){
            int val = mp[weight[j.first]];
            if (!val){
                mp[weight[j.first]] = j.second;
                continue;
            }
            mp[weight[j.first]] = min(val, j.second);
        }
        p.clear();
    }
}

int n;

void best_path(int ns, int ks, int hs[][2], int ls[]){
    n = ns; l = ks;
    for (int i = 0; i < n; i++){
        auto [u, v] = hs[i];
        u++; v++;
        g[u].push_back({v, ls[i]});
        g[v].push_back({u, ls[i]});
    }
    out.assign(n + 1, 0);
    sz.resize(n + 1);
    build(1, 1);
    weight.resize(n + 1);
    used.assign(n + 1, false);
    for (int i = 1; i < lg; i++){
        for (int j: cl[i]){
            solve(j, 1);
        }
    }
    if (ans == msz){
        cout<<-1;
        return;
    }
    cout<<ans;
}
// Old Code

Subtask #1
0 / 9.0

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

Subtask #2
0 / 12.0

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

Subtask #3
0 / 22.0

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

Subtask #4
0 / 57.0

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