Submission #299028

#	Time	Username	Problem	Language	Result	Execution time	Memory
299028		ToMmyDong	Race (IOI11_race)	C++17	100 / 100	798 ms	104056 KiB

race

#include <bits/extc++.h>
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef pair<int,int> pii;
#define ALL(i) i.begin(),i.end()
#define SZ(i) int(i.size())
#define X first
#define Y second
#define eb emplace_back
#define pb push_back
#ifdef tmd
#define debug(...) fprintf(stderr,"#%d-(%s)=",__LINE__,#__VA_ARGS__);_do(__VA_ARGS__);
template<typename T> void _do(T &&x) {cerr<<x<<endl;}
template<typename T, typename ...S> void _do(T &&x, S &&...y) {cerr<<x<<",";_do(y...);}
template<typename IT> ostream& printRng (ostream& os, IT bg, IT ed) {
    os << "{";
    for (IT it=bg; it!=ed; it++) {
        if (it == bg) os << *it;
        else os << "," << *it;
    }
    return os << "}";
}
template<typename T> ostream& operator << (ostream& os, const vector<T>& v) {return printRng(os,ALL(v));}
template<typename T, typename S> ostream& operator << (ostream& os, const map<T,S>& v) {return printRng(os,ALL(v));}
template<typename T, typename S> ostream& operator << (ostream& os, const pair<T,S>& v) {return os<<"("<<v.X<<","<<v.Y<<")";}
#else
#define debug(...)
#endif
#include "race.h"

int n, k;
vector<vector<pii> > edge;
vector<ll> dep;
vector<int> edp;
vector<map<ll,int> > dmp;

const int INF = 0x3f3f3f3f;

int getm (map<ll,int> &mp, ll tg) {
    auto ptr = mp.find(tg);
    if (ptr == mp.end()) return INF;
    else return ptr->Y;
}

int ans = INF;
void dfs (int nd, int par) {
    dmp[nd][dep[nd]] = edp[nd];
    for (auto &[u, w] : edge[nd]) {
        if (u != par) {
            dep[u] = dep[nd] + w;
            edp[u] = edp[nd] + 1;
            dfs(u, nd);

            if (SZ(dmp[nd]) < SZ(dmp[u])) {
                swap(dmp[nd], dmp[u]);
            }

            debug(dmp[nd]);
            for (auto &[dw, de] : dmp[u]) {
                ll rem = k - (dw-dep[nd]) + dep[nd];
                int res = getm(dmp[nd], rem);
                debug(nd, u, de, res, edp[nd]);
                ans = min(ans, de + res - 2*edp[nd]);
            }

            for (auto &[dw, de] : dmp[u]) {
                if (dmp[nd].count(dw)) {
                    int &x = dmp[nd][dw];
                    x = min(x, de);
                } else {
                    dmp[nd][dw] = de;
                }
            }
        }
    }
    debug(nd, dmp[nd]);
}
int best_path(int N, int K, int H[][2], int L[]) {
    n = N;
    k = K;
    edge.resize(N);
    for (int i=0; i<n-1; i++) {
        int u, v, w;
        u = H[i][0];
        v = H[i][1];
        w = L[i];
        edge[u].eb(v, w);
        edge[v].eb(u, w);
    }
    dep.resize(n);
    edp.resize(n);
    dmp.resize(n);
    dfs(0, -1);
    return ans <= n ? ans : -1;
}

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