Submission #98087

#	Time	Username	Problem	Language	Result	Execution time	Memory
98087		SpeedOfMagic	Race (IOI11_race)	C++17	100 / 100	916 ms	46692 KiB

race

#include <bits/stdc++.h>
#include "race.h"
using namespace std;
template<typename T> using v = vector<T>;
typedef vector<int> vint;
#define rep(a, l, r) for(int a = (l); a < (r); a++)
#define pb push_back
#define fs first
#define sc second
#define sz(a) ((int) a.size())
//code starts here
const int maxN = 2e5 + 1;
char vis[maxN];
int siz[maxN];
v<pair<int, int>> t[maxN];

int calcSiz(int cur, int p) {
    siz[cur] = 1;
    for (auto i : t[cur])
        if (i.fs != p && !vis[i.fs])
            siz[cur] += calcSiz(i.fs, cur);
    return siz[cur];
}

const int maxK = 1e6 + 1;
pair<pair<int, int>, pair<int, int>> d[maxK];
int version[maxK];
int curVersion = 0;

int num;
int k;
int added[maxN];
int ptr = 0;
pair<pair<int, int>, pair<int, int>> init = {{maxN, -1}, {maxN, -1}};
void add(int cur, int curDist, int h, int p) {
    if (curDist > k)
        return;

    if (curVersion != version[curDist]) {
        d[curDist] = init;
        version[curDist] = curVersion;
    }
    if (h < d[curDist].fs.fs) {
        if (d[curDist].fs.sc == -1 && curDist <= k / 2)
            added[ptr++] = curDist;
        if (d[curDist].fs.sc != num)
            d[curDist].sc = d[curDist].fs;
        d[curDist].fs = make_pair(h, num);
    } else if (h < d[curDist].sc.fs && d[curDist].fs.sc != num)
        d[curDist].sc = make_pair(h, num);

    for (auto i : t[cur])
        if (i.fs != p && !vis[i.fs])
            add(i.fs, curDist + i.sc, h + 1, cur);
}

int ans = maxN + 5;

inline void find_centroid(int cur) {
    int lim = calcSiz(cur, -1) / 2;
    bool again = 1;
    int pr = -1;
    while (again) {
        again = 0;
        for (auto i : t[cur])
            if (i.fs != pr && !vis[i.fs] && siz[i.fs] > lim) {
                pr = cur;
                cur = i.fs;
                again = 1;
                break;
            }
    }

    ptr = 0;
    vis[cur] = 1;
    curVersion++;
    num = 0;

    added[ptr++] = 0;
    d[0] = {{0, -2}, {maxN, -1}};
    for (auto i : t[cur])
        if (!vis[i.fs]) {
            add(i.fs, i.sc, 1, cur);
            num++;
        }

    rep(z, 0, ptr) {
        int i = added[z];
        int o = k - i;
        if (curVersion != version[o]) {
            d[o] = init;
            version[o] = curVersion;
        }

        if (d[i].fs.sc != d[o].fs.sc)
            ans = min(ans, d[i].fs.fs + d[o].fs.fs);
        else {
            if (d[i].fs.sc != d[o].sc.sc)
                ans = min(ans, d[i].fs.fs + d[o].sc.fs);
            if (d[i].sc.sc != d[o].fs.sc)
                ans = min(ans, d[i].sc.fs + d[o].fs.fs);
            if (d[i].sc.sc != d[o].sc.sc)
                ans = min(ans, d[i].sc.fs + d[o].sc.fs);
        }
    }

    for (auto i : t[cur])
        if (!vis[i.fs])
            find_centroid(i.fs);
}

int best_path(int N, int K, int H[][2], int L[]) {
    k = K;
    memset(vis, 0, sizeof vis);
    memset(version, 0, sizeof version);

    rep(i, 0, N - 1) {
        t[H[i][0]].pb({H[i][1], L[i]});
        t[H[i][1]].pb({H[i][0], L[i]});
    }

    find_centroid(0);
    if (ans >= maxN)
        return -1;
    else
        return ans;
} 

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