Submission #479640

#	Time	Username	Problem	Language	Result	Execution time	Memory
479640		Karliver	Race (IOI11_race)	C++17	0 / 100	3 ms	4940 KiB

race

    
#include <bits/stdc++.h>

#define FIXED_FLOAT(x)  std::fixed <<std::setprecision(20) << (x)
#define all(v) (v).begin(), (v).end()
using namespace  std;
#define forn(i,n) for (int i = 0; i < (n); ++i)
#define rforn(i, n) for(int i = (n) - 1;i >= 0;--i)
#define sz(x) (int)x.size()

using ll = long long;
int mod = (ll)1e9 + 7;
#define PI acos(-1)
typedef pair<int, int> pairs;

const int INF = 1e9 + 1;
const int MX = 2e5 + 100;
const double eps = 1e-7;

template <class T> using V = vector<T>;  
template <class T> using VV = V<V<T>>;  
template<class T, size_t SZ> using AR = array<T, SZ>;
template<class T> using PR = pair<T, T>;
template <typename XPAX>
bool ckma(XPAX &x, XPAX y) {
    return (x < y ? x = y, 1 : 0);
}
template <typename XPAX>
bool ckmi(XPAX &x, XPAX y) {
    return (x > y ? x = y, 1 : 0);
}
const int B = 1e6 + 5;

ll len[MX];
int ms[MX], dep[MX], K;
VV<PR<int>> g(MX);

int ti[B], bes[B];

void dfs1(int v) {
    ms[v] = 1;
    for(auto &c : g[v]) {
        dep[c.first] = dep[v] + 1;
        len[c.first] = len[v] + c.second;
        g[c.first].erase(find(all(g[c.first]), make_pair(v, c.second)));
        dfs1(c.first);
        ms[v] += ms[c.first];
        if(ms[c.first] > ms[g[v][0].first])swap(g[v][0],  c);
    }
}

V<int> tmp;
int ret, timer = 1;
void add(int a) {
    for(auto c : tmp) {
        ll rr = K - (len[c] - len[a]);
        int p = rr % B;
        if(ti[p] != timer)continue;
        if(len[bes[p]] == rr)
            ckmi(ret, dep[bes[p]] + dep[c] - 2 * dep[a]);
    }

    for(auto &c : tmp) {
        int p = len[c] % B;
        if(ti[p] != timer) {
            bes[p] = c;
            ti[p] = timer;
        }
        else if(len[bes[p]] != len[c]) {
            if(len[c] < len[bes[p]])swap(bes[p], c);
        }
        else {
            if(dep[c] < dep[bes[p]])swap(bes[p], c);
        }
    }
    tmp.clear();
}
void get_list(int v) {
    tmp.push_back(v);
    for(auto c : g[v])
        get_list(c.first);
}

void dfs2(int v) {
    rforn(i, sz(g[v])) {
        dfs2(g[v][i].first);
        if(i)
            ++timer;
    }

    tmp = {v};
    add(v);
    for(int i = 1;i < sz(g[v]);++i) {
        get_list(g[v][i].first);
        add(v);
    }
}

int best_path(int N, int _K, int H[][2], int L[]) {
    K = _K;

    forn(i, N - 1) {
        g[H[i][0]].push_back({H[i][1], L[i]});
        g[H[i][1]].push_back({H[i][0], L[i]});
    }
    dfs1(0);

    ret = N;
    dfs2(0);
    
    if(ret == N)
        ret = -1;
    return ret;
}

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