Submission #1148550

#	Time	Username	Problem	Language	Result	Execution time	Memory
1148550		trytovoi	Race (IOI11_race)	C++20	0 / 100	7 ms	16960 KiB

race

#include <bits/stdc++.h>
using namespace std;

// #define LOCAL

#ifdef LOCAL
#include "debug2.h"
#else
#define debug(...) 42
#endif

template<typename T> bool ckmin(T& x, const T& y) { return x > y ? x = y, 1 : 0; } 
template<typename T> bool ckmax(T& x, const T& y) { return x < y ? x = y, 1 : 0; } 

#define REP(i, n) for(int i = 0, ____n = (n); i < ____n; ++i)
#define REPD(i, n) for(int i = (n) - 1; i >= 0; --i)
#define left  _______left
#define right _______right
#define MASK(x) (1LL << (x))
#define BIT(mask, x) (((mask) >> (x)) & 1)
#define SZ(x) (int) ((x).size())
#define ALL(x) (x).begin(), (x).end()
#define RALL(x) (x).rbegin(), (x).rend()
#define SQR(x) (1LL * (x) * (x))
#define BETWEEN(l, x, r) ((l) <= (x) && (x) <= (r))
#define pb push_back

const long long INF = (long long) 1e18 + 7;
const int MOD = (int) 1e9 + 7;
const int MX = (int) 2e5 + 5;
const int LG = __lg(MX) + 1;
const int BLOCK = 320;
const int MAX_K = (int) 1e6 + 5;

int N, K;
vector<pair<int, int>> adj[MX];
int sz[MX];
bool del[MX];

void countChild(int u, int p) {
    sz[u] = 1;
    for (auto [v, l] : adj[u]) if (v != p && !del[v]) {
        countChild(v, u);
        sz[u] += sz[v];
    }
}

int centroid(int u, int p, int n) {
    for (auto [v, l] : adj[u]) if (v != p && !del[v] && sz[v] > n / 2) return centroid(v, u, n);
    return u;
}

vector<pair<int, int>> vec;
int timer = 0;
int exist[MAX_K];
long long ans;
long long min_dep[MAX_K];

void dfs(int u, int p, int dep, int len) {
    if (len > K) return;
    vec.pb(make_pair(dep, len));
    if (exist[K - len] == timer) ckmin(ans, min_dep[K - len] + dep);
    for (auto [v, l] : adj[u]) if (v != p && !del[v]) {
        dfs(v, u, dep + 1, len + l);
    }
}

void getAns(int root, int n) {
    ++timer;
    exist[0] = timer;
    for (auto [v, l] : adj[root]) if (!del[v]) {
        vec.clear(); // (dep, len)
        dfs(v, root, 1, l);
        for (auto [dep, len] : vec) {
            if (exist[len] != timer || (exist[len] == timer && min_dep[len] > dep)) {
                exist[len] = timer;
                min_dep[len] = dep;
            }
        }
    }
}

void solve(int u) {
    countChild(u, -1);
    int n = sz[u];
    int root = centroid(u, -1, n);
    getAns(root, n);
    del[root] = true;
    for (auto [v, l] : adj[root]) if (!del[v]) solve(v);
}

int best_path(int n, int k, int edges[][2], int weights[]) {
    N = n; K = k;
    for (int i = 1; i < N; ++i) {
        int u = edges[i][0] + 1, v = edges[i][1] + 1;
        int l = weights[i];
        adj[u].pb(make_pair(v, l));
        adj[v].pb(make_pair(u, l));
    }

    memset(del, false, sizeof del);
    memset(exist, -1, sizeof exist);
    memset(min_dep, 0x3f, sizeof min_dep);
    min_dep[0] = 0;
    vec.clear();

    ans = INF;
    solve(1);
    
    return ans == INF ? -1 : ans;
}

/**



**/

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