Submission #856955

#	Time	Username	Problem	Language	Result	Execution time	Memory
856955		hngwlog	Race (IOI11_race)	C++14	21 / 100	99 ms	35156 KiB

race

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

#define fi first
#define se second
#define _size(x) (int)x.size()
#define BIT(i, x) ((x >> i) & 1)
#define MASK(n) ((1 << n) - 1)
#define REP(i, n) for (int i = 0, _n = (n); i < _n; i++)
#define FOR(i, a, b) for (int i = a, _b = (b); i <= _b; i++)
#define FORD(i, a, b) for (int i = a, _b = (b); i >= _b; i--)
#define FORB1(i, mask) for (int i = mask; i > 0; i ^= i & - i)
#define FORB0(i, n, mask) for (int i = ((1 << n) - 1) ^ mask; i > 0; i ^= i & - i)
#define FORALL(i, a) for (auto i: a)
#define fastio ios_base::sync_with_stdio(0); cin.tie(0);

const int inf = 1e9;

struct edgeNode {

    int u, v;
    long long w;
};

int ans = inf;
vector<int> used, depth, inSt;
vector<long long> dist;
vector<edgeNode> edge;
vector<vector<int>> adj;
vector<set<pair<long long, int>>> st;

void connect(int id) {

    adj[edge[id].u].push_back(id);
    adj[edge[id].v].push_back(id);
}

void dfs(int u, long long k) {

    int bestV = - 1;
    vector<int> vtx;
    FORALL(id, adj[u]) {
        if (used[id]) continue;
        used[id]++;
        int v = edge[id].u + edge[id].v - u;
        long long w = edge[id].w;
        depth[v] = depth[u] + 1;
        dist[v] = dist[u] + w;
        dfs(v, k);
        if (bestV == - 1 || _size(st[bestV]) < _size(st[inSt[v]])) bestV = inSt[v];
        vtx.push_back(v);
    }
    if (bestV == - 1) {
        inSt[u] = u;
        st[u].insert({dist[u], depth[u]});
        return ;
    }
    FORALL(v, vtx) {
        if (inSt[v] == bestV) continue;
        FORALL(e, st[inSt[v]]) {
            auto it = st[bestV].lower_bound({k + dist[u] * 2 - e.fi, 0});
            if (it != st[bestV].end() && it->fi == k + dist[u] * 2 - e.fi) ans = min(ans, e.se + it->se - 2 * depth[u]);
        }
        FORALL(e, st[inSt[v]]) {
            if (e.fi - dist[u] > k) continue;
            st[bestV].insert(e);
        }
    }
    auto it = st[bestV].lower_bound({k + dist[u], 0});
    if (it->fi == k + dist[u]) ans = min(ans, it->se - depth[u]);
    inSt[u] = bestV;
    st[bestV].insert({dist[u], depth[u]});
}

int best_path(int n, int k, int h[][2], int l[]) {

    edge.resize(n - 1);
    adj.resize(n);
    REP(i, n - 1) {
        edge[i] = {h[i][0], h[i][1], l[i]};
        connect(i);
    }
    used.resize(n - 1);
    depth.resize(n);
    dist.resize(n);
    inSt.resize(n);
    st.resize(n);
    dfs(0, k);
    return ans == inf ? - 1 : ans;
}

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