Submission #558598

#	Time	Username	Problem	Language	Result	Execution time	Memory
558598		dooompy	Race (IOI11_race)	C++17	0 / 100	8 ms	10012 KiB

race

#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;

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);
    }
}

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);
    }
}

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][0], b = H[i][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];

    dfs(1);

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

//int 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 = 0; 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 = 0; i < n-1;i++) cin>> l[i];
//
//    dfs(0);
//
//    if (ans >= n +1) {
//        cout << -1;
//    } else cout << ans;
//}

Compilation message (stderr)

race.cpp: In function 'int find_size(int, int)':
race.cpp:65:1: warning: control reaches end of non-void function [-Wreturn-type]
   65 | }
      | ^

• Subtask 1: 0 / 9
• Subtask 2: 0 / 12
• Subtask 3: 0 / 22
• Subtask 4: 0 / 57