Submission #541605

#	Time	Username	Problem	Language	Result	Execution time	Memory
541605		Evang	Race (IOI11_race)	C++17	21 / 100	3096 ms	14144 KiB

race

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

#ifdef _DEBUG
#define dout(x) clog << "Line " << __LINE__ << ": " << #x << "=" << (x) << el
#else
#define dout(x)
#endif

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define uid(a,b) uniform_int_distribution<int>(a,b)(rng)

#define ins insert
#define ssize(x) (int((x).size()))
#define bs(args...) binary_search(args)
#define lb(args...) lower_bound(args)
#define ub(args...) upper_bound(args)
#define all(x) (x).begin(),(x).end()
#define mp(a, b) make_pair(a, b)
#define mt(args...) make_tuple(args)
#define pb push_back
#define eb emplace_back
#define ff first
#define ss second
#define die exit(0)

template<typename T>
using vc = vector<T>;
template<typename T>
using uset = unordered_set<T>;
template<typename A, typename B>
using umap = unordered_map<A, B>;
template<typename T, typename Comp>
using pq = std::priority_queue<T, vc<T>, Comp>;
template<typename T>
using maxpq = pq<T, less<T>>;
template<typename T>
using minpq = pq<T, greater<T>>;
template<typename T>
using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

using db = double;
using ld = long double;
using ll = long long;
using ull = unsigned long long;
using pi = pair<int, int>;
using pll = pair<ll, ll>;
using vi = vc<int>;
using vll = vc<ll>;
using vpi = vc<pi>;
using vpll = vc<pll>;
using str = string;

constexpr char el = '\n';
constexpr char sp = ' ';
constexpr int inf = 0x3f3f3f3f;
constexpr ll llinf = 0x3f3f3f3f3f3f3f3fLL;
// ---------------------------------------------------------------------


const int N = 2e5+5;
const int K = 1e6+5;
int n, k, a[K], ans = inf, sub[N];
vpi adj[N];
bitset<N> r;

void dfs(int v, int p){
    if(r[v]) {
        sub[v] = 0;
        return;
    }

    sub[v] = 1;
    for(auto[u, w]: adj[v]){
        if(u==p)
            continue;
        dfs(u, v);
        sub[v] += sub[u];
    }
}

int get_centroid(int v, int p, int sz){
    for(auto[u, _]: adj[v])
        if(!r[u]&&u!=p&&sub[u]*2>sz)
            return get_centroid(u, v, sz);
    return v;
}

void upd_ans(int v, int p, ll dis, int dep){
    if(r[v]||dis>k||dep>ans)
        return;
    ans = min(ans, a[k-dis]+dep);
    for(auto[u, w]: adj[v])
        if(u!=p)
            upd_ans(u, v, dis+w, dep+1);
}

void upd_a(int v, int p, ll dis, int dep){
    if(r[v]||dis>k||dep>ans)
        return;
    a[dis] = min(a[dis], dep);
    for(auto[u, w]: adj[v])
        if(u!=p)
            upd_a(u, v, dis+w, dep+1);
}

void reset(int v, int p, ll dis){
    if(r[v]||dis>k)
        return;
    a[dis] = inf;
    for(auto[u, w]: adj[v])
        if(u!=p)
            reset(u, v, dis+w);
}

void solve(int v){
    if(r[v])
        return;
    dfs(v, -1);
    int c = get_centroid(v, -1, sub[v]);
    r[c] = 1;
    for(auto[u, w]: adj[c]){
        upd_ans(u, c, w, 1);
        upd_a(u, c, w, 1);
    }
    for(auto[u, w]: adj[c])
        reset(u, c, w);
    a[0] = 0;

    for(int i = 1; i < K; ++i)
        assert(a[i]==inf);

    for(auto[u, _]: adj[c])
        solve(u);
}

int best_path(int _n, int _k, int h[][2], int l[]) {
    n = _n;
    k = _k;
    for(int i = 0; i +1 < n; ++i) {
        adj[h[i][0]].eb(h[i][1], l[i]);
        adj[h[i][1]].eb(h[i][0], l[i]);
    }
    memset(a, 0x3f, sizeof a);
    a[0] = 0;
    solve(0);
    if(ans==inf)
        return -1;
    return ans;
}

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