Submission #499794

#	Time	Username	Problem	Language	Result	Execution time	Memory
499794		zxcvbnm	Race (IOI11_race)	C++14	0 / 100	3 ms	4940 KiB

race

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

constexpr int nax = 2e5 + 5;
vector<pair<int, int>> adj[nax];
int k;

struct Centroid {
    vector<int> sz;
    vector<bool> vis;
    int ans = INT_MAX;

    void init(int n) {
        sz.resize(n);
        vis.assign(n, false);
    }

    int find_size(int v, int p=-1) {
        if (vis[v]) {
            return 0;
        }

        sz[v] = 1;
        for(auto u : adj[v]) {
            if (u.first == p) continue;
            sz[v] += find_size(u.first, v);
        }
        return sz[v];
    }

    int find_centroid(int v, int p, int n) {
        for(auto u : adj[v]) {
            if (u.first == p || vis[u.first]) continue;
            if (sz[u.first] > n/2) {
                return find_centroid(u.first, v, n);
            }
        }
        return v;
    }

    map<int, int> mp;

    void dfs(int v, int p, int depth, int cost, bool filling) {
        if (cost > k) return;
//        cerr << "v: " << depth << " " << cost << "\n";
        if (cost == k) {
            ans = min(ans, depth);
            return;
        }

        if (filling) {
            if (mp.find(cost) == mp.end() || mp[cost] > depth) {
                mp[cost] = depth;
            }
        }
        else {
            if (mp.find(k-cost) != mp.end()) {
                ans = min(ans, depth + mp[k-cost]);
//                cerr << "in: " << depth + mp[k-cost] << "\n";
            }
        }

        for(auto u : adj[v]) {
            if (u.first == p || vis[u.first]) continue;
//            dfs(u.first, v, depth+1, cost+u.second, filling);
        }
    }

    void sol(int v) {
        mp.clear();

        for(auto u : adj[v]) {
            if (vis[u.first]) continue;
//            cout << v << "->" << u.first << " cost " << u.second << "\n";
            dfs(u.first, v, 1, u.second, false);
            dfs(u.first, v, 1, u.second, true);
        }
    }

    void init_centroid(int v=0, int p=-1) {
        find_size(v);

        int c = find_centroid(v, p, sz[v]);
        vis[c] = true;
        sol(c);
//        cout << c << " " << ans << "\n";

        for(auto u : adj[c]) {
            if (!vis[u.first]) {
                init_centroid(u.first, c);
            }
        }
    }
};

int best_path(int N, int K, int H[][2], int L[])
{
    k = K;
    for(int i = 0; i < N-1; i++) {
        adj[H[i][0]].push_back({H[i][1], L[i]});
        adj[H[i][1]].push_back({H[i][0], L[i]});
    }

    Centroid ct;
    ct.init(N+6);
    ct.init_centroid();
    return ct.ans == INT_MAX ? -1 : ct.ans;
}

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