제출 #393297

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
393297		MarcoMeijer	경주 (Race) (IOI11_race)	C++14	100 / 100	2613 ms	88312 KiB

race

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

// macros
typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
typedef pair<ll, ll> lll;
typedef tuple<int, int, int> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<iii> viii;
typedef vector<ll> vll;
typedef vector<lll> vlll;
#define REP(a,b,c) for(int a=int(b); a<int(c); a++)
#define RE(a,c) REP(a,0,c)
#define RE1(a,c) REP(a,1,c+1)
#define REI(a,b,c) REP(a,b,c+1)
#define REV(a,b,c) for(int a=int(c-1); a>=int(b); a--)
#define FOR(a,b) for(auto& a : b)
#define all(a) a.begin(), a.end()
#define INF 1e9
#define EPS 1e-9
#define pb push_back
#define popb pop_back
#define fi first
#define se second

int best_path(int N, int K, int H[][2], int L[]) {
    vector<vll> adj; adj.resize(N);
    vector<vlll> adjW; adjW.resize(N);
    vector<bool> ignore; ignore.assign(N,0);
    vll sz; sz.assign(N,0);
    map<ll,vlll> mp;
    ll ans = N+1;

    RE(i,N-1) RE(j,2) adj [H[i][j]].push_back(H[i][!j]);
    RE(i,N-1) RE(j,2) adjW[H[i][j]].push_back({H[i][!j], L[i]});

    std::function<void(ll,ll)> dfsSize;
    std::function<ll(ll,ll,ll)> dfsCentroid;
    std::function<void(ll,ll,ll,ll,ll)> dfsMap;
    std::function<void(ll)> centroidDecomp;

    dfsSize = [&](ll u, ll p) {
        sz[u] = 1;
        FOR(v,adj[u]) {
            if(ignore[v]) continue;
            if(v == p) continue;
            dfsSize(v,u);
            sz[u] += sz[v];
        }
    };
    dfsCentroid = [&](ll u, ll p, ll maxSize) {
        FOR(v,adj[u]) {
            if(ignore[v]) continue;
            if(v == p) continue;
            if(sz[v] > maxSize) return dfsCentroid(v,u,maxSize);
        }
        return u;
    };
    dfsMap = [&](ll u, ll p, ll root, ll len, ll depth) {
        mp[depth].push_back({len,root});
        FOR(v,adjW[u]) {
            if(ignore[v.fi]) continue;
            if(v.fi == p) continue;
            dfsMap(v.fi,u,root,len+1,depth+v.se);
        }
    };
    auto findCentroid = [&](ll u) {
        dfsSize(u,-1);
        return dfsCentroid(u,-1,sz[u]/2);
    };
    centroidDecomp = [&](ll u) {
        ll cent = findCentroid(u);
        mp.clear();
        FOR(v,adjW[cent]) {
            if(ignore[v.fi]) continue;
            dfsMap(v.fi,cent,v.fi,1,v.se);
        }
        mp[0].push_back({0,-2});
        FOR(p,mp) {
            sort(all(p.se));
            lll a={-1,-1}, b={-1,-1};
            vlll newF;
            FOR(np,p.se) {
                if(a.se == np.se || b.se == np.se) continue;
                if(a.fi == -1) {
                    a = np; newF.push_back(np);
                } else if(b.fi == -1) {
                    b = np; newF.push_back(np);
                }
            }
            p.se = newF;
        }
        FOR(p,mp) {
            auto& f1 = p.se;
            auto& f2 = mp[K - p.fi];
            FOR(i,f1) FOR(j,f2) if(i.se != j.se) ans = min(ans, i.fi + j.fi);
        }

        // recursive
        ignore[cent] = 1;
        FOR(v,adj[cent]) {
            if(ignore[v]) continue;
            centroidDecomp(v);
        }
    };

    centroidDecomp(0);

    if(ans == N+1) ans = -1;

    return ans;
}

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