oj.uz

Submission #558615

# Submission time Handle Problem Language Result Execution time Memory
558615 2022-05-07T15:30:24 Z dooompy Race (IOI11_race) C++17
0 / 100
 3 ms 4948 KB 
#include "bits/stdc++.h"
#include "race.h"

using namespace std;

void abc() {cout << endl;}
template <typename T, typename ...U> void abc(T a, U ...b) {
    cout << a << ' ', abc(b...);
}
template <typename T> void printv(T l, T r) {
    while (l != r) cout << *l << " \n"[++l == r];
}
template <typename A, typename B> istream& operator >> (istream& o, pair<A, B> &a) {
    return o >> a.first >> a.second;
}
template <typename A, typename B> ostream& operator << (ostream& o, pair<A, B> a) {
    return o << '(' << a.first << ", " << a.second << ')';
}
template <typename T> ostream& operator << (ostream& o, vector<T> a) {
    bool is = false;
    for (T i : a) {o << (is ? ' ' : '{'), is = true, o << i;}
    return o << '}';
}

#ifdef local
#define test(args...) abc("[" + string(#args) + "]", args)
#else
#define test(args...) void(0)
#endif

using ll = long long;

#define int ll

vector<pair<int, int>> adj[200005];
int l[200005];
int seen[200005];
int sz[200005];

int timer = 1;
int idx[200005];
int cnt[200005];

int n, k;

int ans;

int find_centroid(int node, int par, int n) {

    for (auto a : adj[node]) {
        if (a.first == par) continue;
        if (!seen[a.first] && sz[a.first] >= n / 2) return find_centroid(a.first, node, n);
    }

    return node;
}

int find_size(int node, int par = -1) {

    if (seen[node]) return 0;

    sz[node] = 1;
    for (auto a : adj[node]) {
        if (a.first == par) continue;
        sz[node] += find_size(a.first, node);
    }

    return sz[node];
}

void dist(int node, int dep, int w, int par, bool ver) {
    for (auto a: adj[node]) {
        if (a.first == par || seen[a.first]) continue;
        dist(a.first, dep + 1, w + l[a.second], node, ver);
    }

    if (!ver) {
        int req = k - w;
        if (idx[req] < timer) {
            idx[req] = timer, cnt[req] = n + 1;
        }
        ans = min(ans, dep + cnt[req]);
    } else {
        int req = w;
        if (idx[req] < timer) {
            idx[req] = timer, cnt[req] = n + 1;
        }
        cnt[req] = min(cnt[req], dep);
    }

}


void dfs(int node, int par = -1) {
    find_size(node);

    int c = find_centroid(node, -1, sz[node]);

    timer++;
    for (auto nxt : adj[c]) {
        if (seen[nxt.first]) continue;
        dist(nxt.first, 1, l[nxt.second], c, false);
        dist(nxt.first, 1, l[nxt.second], c, true);
    }


    seen[c] = true;

    for (auto a : adj[c]) {
        if (seen[a.first]) continue;
        dfs(a.first);
    }
}

#undef int
int best_path(int N, int K, int H[][2], int L[]) {
    n = N, k = K;
    for (int i = 1; i <= n-1; i++) {
        int a = H[i-1][0], b = H[i-1][1];
        a++; b++;
        adj[a].push_back({b, i});
        adj[b].push_back({a, i});
    }

    for (int i = 1; i <= n-1;i++) l[i] = L[i-1];

    dfs(1);

    if (ans >= n +1) {
        return -1;
    } else return ans;
}


//int32_t main() {
//    ios_base::sync_with_stdio(0);
//    cin.tie(0); cout.tie(0);
//    freopen("race.in", "r", stdin);
//    freopen("race.out", "w", stdout);
//    cin >> n >> k;
//    ans = n + 1;
//    for (int i = 1; i <= n-1; i++) {
//        int a, b; cin >> a >> b;
//        adj[a].push_back({b, i}); adj[b].push_back({a, i});
//    }
//
//    for (int i = 1; i <= n-1; i++) cin >> l[i];
//
//    dfs(1);
//
//    if (ans >= n +1) {
//        cout << -1;
//    } else cout << ans;
//}

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 4948 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 4948 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 4948 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 4948 KB Output isn't correct
2 Halted 0 ms 0 KB -