Submission #687676

#	Time	Username	Problem	Language	Result	Execution time	Memory
687676		Bliznetc	Race (IOI11_race)	C++17	0 / 100	5 ms	8936 KiB

race

#include <bits/stdc++.h>
#include "race.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) {
            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 = k - w;
    if (need == 0) {
        ans = min(ans, d);
    }
    if (mn[need] != 1e9) {
        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) {
    calc_sz(c, c);
    int v = get_centroid(c, c, _sz[c]);
    used[v] = 1;

    vector <pii> all_vec;
    for (auto to : g[v]) {
        int i = to.F, w = to.S;
        if (used[i]) {
            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]) {
            continue;
        }
        calc_ans(to);
    }
}

int 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];
        g[u].pb({v, w});
        g[v].pb({u, w});
    }

    for (int i = 0; i < A; i++) {
        mn[i] = 1e9;
    }

    calc_ans(0);

    if (ans == 1e9) {
        ans = -1;
    }
    return ans;
}


//signed main() {
//    int n = 4, k = 3;
//    int h[3][2], l[3];
//    h[0][0] = 0, h[0][1] = 1;
//    h[1][0] = 1, h[1][1] = 2;
//    h[2][0] = 3, h[2][1] = 1;
//    l[0] = 1;
//    l[1] = 2;
//    l[2] = 4;
//    best_path(n, k, h, l);
//
//}

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