Submission #146668

#	Time	Username	Problem	Language	Result	Execution time	Memory
146668		karma	Race (IOI11_race)	C++14	9 / 100	111 ms	24352 KiB

race

#include <bits/stdc++.h>
#include "race.h"
#define Task     "test"
#define ll        long long
#define pb        emplace_back
#define mp        make_pair
#define fi        first
#define se        second

using namespace std;

typedef pair<ll, int> pii;
const int N = int(2e5) + 7;
const int K = int(1e6) + 7;

set<pii>* s[N];
int n, k, u, v, w, res, sz[N], h[N], p[N];
ll d[N];
vector<pii> a[N];

void Build(int u)
{
    sz[u] = 1;
    for(pii adj: a[u]) {
        int v = adj.fi;
        if(v == p[u]) continue;
        p[v] = u, d[v] = d[u] + adj.se;
        h[v] = h[u] + 1, Build(v);
        sz[u] += sz[v];
    }
}

void Insert(set<pii>* s, ll d, int h)
{
     pii found = *(s -> lower_bound(mp(d, -1)));
     if(found.fi == d && found.se <= h) return;
     if(found.fi == d) s -> erase(found);
     s -> insert(mp(d, h));
}

void query(int u, int root)
{
    if(h[u] - h[root] >= res) return;
    int dis = 2 * h[root] + k - h[u];
    pii found = *(s[root] -> lower_bound(mp(dis, -1)));
    if(found.se + h[u] - 2 * h[root] < res) res = found.se + h[u] - 2 * h[root];
    for(pii adj: a[u])
        if(adj.fi != p[u]) query(adj.fi, root);
}

void add(int u, int root)
{
    if(h[u] - h[root] >= res) return;
    Insert(s[root], d[u], h[u]);
    for(pii adj: a[u])
        if(adj.fi != p[u]) add(adj.fi, root);
}

void DSU(int u)
{
     int bigC = -1;
     for(pii adj: a[u]) {
        if(adj.fi == p[u]) continue;
        if(bigC == -1 || sz[adj.fi] > sz[bigC]) bigC = adj.fi;
     }
     for(pii adj: a[u]) {
        if(bigC == adj.fi || adj.fi == p[u]) continue;
        DSU(adj.fi);
     }
     if(bigC != -1) DSU(bigC), s[u] = s[bigC];
     else s[u] = new set<pii>(), s[u] -> clear();
     pii found = *(s[u] -> lower_bound(mp(d[u] + k, -1)));
     if(found.fi == d[u] + k) res = min(res, found.se - h[u]);
     Insert(s[u], d[u], h[u]);
     for(pii adj: a[u]) {
        if(bigC == adj.fi || adj.fi == p[u]) continue;
        query(adj.fi, u);
        add(adj.fi, u);
     }
}

int best_path(int N, int K, int _h[][2], int _l[])
{
    n = N, k = K;
    for(int i = 0, lim = n - 1; i < lim; ++i)
       if(_l[i] <= K) a[_h[i][0]].pb(_h[i][1], _l[i]), a[_h[i][1]].pb(_h[i][0], _l[i]);
    res = n + 1;
    Build(0), DSU(0);
    if(res == n + 1) return -1;
    return res;
}

/*int _h[N][2], _n, _k, _l[N];

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    if(fopen(Task".inp", "r")) {
        freopen(Task".inp", "r", stdin);
        freopen(Task".out", "w", stdout);
    }

    cin >> _n >> _k;
    for(int i = 0; i < _n - 1; ++i) {
        cin >> _h[i][0] >> _h[i][1] >> _l[i];
    }
    cout << best_path(_n, _k, _h, _l);

    return 0;
}*/

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