Submission #687717

#	Time	Username	Problem	Language	Result	Execution time	Memory
687717		Bliznetc	Race (IOI11_race)	C++17	9 / 100	27 ms	4116 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 = 101, A = 101;
vector <vector <pii> > g(N);
int _sz[N], used[N];
int mn[A];
 
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 (!used[to] && to != pr && _sz[to] > n / 2) {
            return get_centroid(to, v, n);
        }
    }
    return v;
}
 
int ans = 1e9;
vector <pii> vec;
void dfs (int v, int w, int pr, int d, int k) {
    if (w > k) {
        return;
    }
    int need = k - w;
    if (need == 0) {
        ans = min(ans, d);
    }
    if (mn[need] != 1e9) {
        ans = min(ans, mn[need] + d);
    }
    vec.pb({w, d});
    for (auto i : g[v]) {
        int to = i.F, w1 = i.S;
        if (used[to] || to == pr) {
            continue;
        }
        dfs (to, w + w1, v, d + 1, k);
    }
}
 
void calc_ans (int c, int k) {
    calc_sz(c, c);
    int v = get_centroid(c, c, _sz[c]);
    used[v] = 1;
 
    vector <pii> cur;
    for (auto i : g[v]) {
        int to = i.F, w = i.S;
        if (used[to]) {
            continue;
        }
        dfs (to, w, v, 1, k);
        for(auto j : vec) {
            mn[j.F] = min(mn[j.F], j.S);
            cur.pb(j);
        }
        vec.clear();
    }
 
    for (auto i : cur) {
        mn[i.F] = 1e9;
    }
 
    for (auto i : g[v]) {
        int to = i.F;
        if (used[to]) {
            continue;
        }
        calc_ans(to, k);
    }
}
 
int best_path (int N, int K, int h[][2], int l[]) {
    int n = N;
    int k = K;
    for (int i = 0; i < n - 1; 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, k);
 
    if (ans == 1e9) {
        ans = -1;
    }
    return ans;
}
 

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