Submission #687624

#	Time	Username	Problem	Language	Result	Execution time	Memory
687624		Bliznetc	Race (IOI11_race)	C++17	0 / 100	4 ms	8916 KiB

race

#include <bits/stdc++.h>

#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-O3")
#pragma GCC target("avx2")

using namespace std;

#define pb push_back
#define sz size()
#define all(x) x.begin(), x.end()
#define F first
#define S second

typedef pair < int, int > pii;
typedef vector < int >  vi;
typedef vector < vi >  vvi;

const int N = 200200, A = 1000001;
int _sz[N], used[N], mn[A];
vector <vector <pii > > g(N);

void calc_sz (int v, int pr) {
    _sz[v] = 1;
    for (auto i : g[v]) {
        int to = i.F;
        if (used[to] || to == pr) {
            continue;
        }
        calc_sz(to, v);
        _sz[v] += _sz[to];
    }
}

int get_centroid (int v, int pr, int n) {
    for (auto i : g[v]) {
        int to = i.F;
        if (to == pr || used[to] || _sz[to] < n / 2) {
            continue;
        }
        return get_centroid(to, v, n);
    }
    return v;
}

int n, k, ans = 1e9;
vector<pii> vec;
void dfs (int v, int pr, int w, int d) {
    if (w > k) {
        return;
    }
    int need = w - k;
    if (need == 0) {
        ans = min(ans, d);
    }
    ans = min(ans, d + mn[need]);
    vec.pb({w, d});
    for (auto i : g[v]) {
        int to = i.F, w1 = i.S;
        if (used[to] || to == pr) {
            continue;
        }
        dfs (to, v, w + w1, d + 1);
    }
}

void calc_ans (int c, int pr) {
    calc_sz(c, pr);
    int v = get_centroid(c, pr, _sz[c]);
    used[v] = 1;

    vector <pii> all_vec;
    for (auto to : g[v]) {
        int i = to.F, w = to.S;
        if (used[i] || i == pr) {
            continue;
        }
        dfs (i, v, w, 1);
        for (auto j : vec) {
            mn[j.F] = min(mn[j.F], j.S);
            all_vec.pb(j);
        }
        vec.clear();
    }

    for (auto i : all_vec) {
        mn[i.F] = 1e9;
    }

    for (auto i : g[v]) {
        int to = i.F;
        if (used[to] || to == pr) {
            continue;
        }
        calc_ans(to, v);
    }
}

void best_path (int N, int K, int h[][2], int l[]) {
    n = N;
    k = K;
    for (int i = 0; i < n; i++) {
        int u = h[i][0], v = h[i][1], w = l[i];
        u++, v++;
        g[u].pb({v, w});
        g[v].pb({u, w});
    }

    for (int i = 0; i < A; i++) {
        mn[i] = 1e9;
    }
    calc_ans(1, 1);
    if (ans >= 1e9) {
        ans = -1;
    }
    cout << ans;
}

/*
signed main() {
    int n = 4, k = 3;
    int h[]
    /*ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int t = 1;
    cin >> t;
    while (t--) {
        solve();
        cout << "\n";
    }
}

*/

Compilation message (stderr)

race.cpp:123:5: warning: "/*" within comment [-Wcomment]
  123 |     /*ios_base::sync_with_stdio(false);
      |

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