Submission #63116

#	Time	Username	Problem	Language	Result	Execution time	Memory
63116		FLDutchman	경주 (Race) (IOI11_race)	C++14	100 / 100	2422 ms	101000 KiB

race

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

typedef int INT;

#define int long long
#define pb push_back
#define fst first
#define snd second
#define FOR(i, l, r) for(int i = (l); i < (r); i++)
#define V vector

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> ii;
typedef vector<ii> vii;

struct edge {int v, l;};

int N, K;
V<V<edge>> adj;
V<bool> used;

int centroid(int u, int par, int &root, int size){
    //if(u == par) cout << "calling centroid " << u << " " << size << endl;
    int sz = 1;
    int ma = 0;
    for(edge e : adj[u]) if(!used[e.v] and e.v != par) {
        int s = centroid(e.v, u, root, size);
        sz += s;
        ma = max(ma, s);
    }
    //if(size != 0) 
    //    cout << "largest " << max(ma, size-sz) << endl;
    if(max(ma, size-sz) <= size/2) root = u;
    //if(size != 0) cout << u << " " << par << " " << sz << endl;
    return sz;
}

void dfs(int u, int par, int d, int l, vii &paths){
    //cout << "dfs " << u << " " << par << endl;
    paths.pb({d, l});
    for(edge e : adj[u]) if(!used[e.v] and e.v != par) dfs(e.v, u, d+e.l, l+1, paths);
}

int shortest(int u){
    //cout << "shortest " << u << endl;
    int root, sz;
    sz = centroid(u, u, root, 0);
    centroid(u, u, root, sz);
    //cout << "root " << root << " " << sz << endl;
    used[root] = 1;
    map<int, int> paths;
    int best = 1e9;
    for(edge e : adj[root]) if(!used[e.v]) {
        vii pa;
        dfs(e.v, root, e.l, 1, pa);
        for(ii p : pa){
            int &l = paths[ K - p.fst ];
            if(l != 0) best = min(best, p.snd + l);
            if(p.fst == K) best = min(best, p.snd);
        }
        for(ii p : pa){
            int &l = paths[p.fst];
            if(l == 0) l = p.snd;
            else l = min(l, p.snd);
        }
    }
    for(edge e : adj[root]) if(!used[e.v]) best = min(best, shortest(e.v));
    return best;
}

INT best_path(INT n, INT k, INT H[][2], INT L[]) {
    N = n; K = k;
    adj.resize(N);
    used.assign(N, 0);
    FOR(i, 0, N-1) {
        //if(L[i] + L[i+1] == K) {cerr << i << endl; return 2;}
        adj[H[i][0]].pb({H[i][1], L[i]});
        adj[H[i][1]].pb({H[i][0], L[i]});
    }
    int res = shortest(0);
    return res == 1e9 ? -1 : res;
}

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