제출 #393292

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
393292		MarcoMeijer	경주 (Race) (IOI11_race)	C++14	21 / 100	531 ms	26180 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,-1});
        FOR(p,mp) {
            sort(all(p.se));
            p.se.erase(unique(all(p.se)), p.se.end());
            if(p.se.size() > 2)
                p.se.resize(2);
        }
        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: 0 / 22
• Subtask 4: 0 / 57