제출 #343162

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

race

#include "race.h"
#include <bits/stdc++.h>

using namespace std;

#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define REP(n) FOR(O, 1, (n))
#define f first
#define s second
#define pb push_back
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pii> vii;
typedef long long ll;

const int MAXN = 1000100;

int n, k;
vii adj[MAXN];
int ans = -1;
bool vis[MAXN];
int sz[MAXN];
//vi reach;
int c = -1;
//vector<pair<int, ll>> paths;
//unordered_map<int, int> minLen;
int minLen[MAXN];
vi changed;

void calcSizes (int v, int p = -1) {
    sz[v] = 1;
    //reach.pb(v);
    for (auto pp : adj[v]) {
        int u = pp.f;
       // ll w = pp.s;
        if (u == p) continue;
        if (vis[u]) continue;
        calcSizes(u, v);
        sz[v] += sz[u];
    }
}

void findCentroid (int v, int allSz, int p = -1) {
    bool can = true;
    for (auto pp : adj[v]) {
        int u = pp.f;
        //ll w = pp.s;
        if (u == p) continue;
        if (vis[u]) continue;
        findCentroid(u, allSz, v);

        if (sz[u] > allSz/2) can = false;
    }

    if ((allSz - sz[v]) > allSz/2) can = false;

    if (can) c = v;
}

void getPaths (int v, ll len, int dep, int p = -1) {

    for (auto pp : adj[v]) {
        int u = pp.f;
        ll w = pp.s;
        if (u == p) continue;
        if (vis[u]) continue;
        getPaths(u, len+w, dep+1, v);
    }
    //paths.pb({dep, len});

    if (len <= k) {
        int remLen = k - len;
        if (minLen[remLen] != -1) {
            int dep2 = minLen[remLen] + dep;
            if (ans == -1) ans = dep2;
            else ans = min(ans, dep2);
        }
    }
}

void getPaths2 (int v, ll len, int dep, int p = -1) {

    for (auto pp : adj[v]) {
        int u = pp.f;
        ll w = pp.s;
        if (u == p) continue;
        if (vis[u]) continue;
        getPaths2(u, len+w, dep+1, v);
    }
    //paths.pb({dep, len});

    if (len < k) {
        if (minLen[len] == -1) minLen[len] = dep;
        else minLen[len] = min(minLen[len], dep);
        changed.pb(len);
    }
}

void trav (int v) {

    //reach.clear();
    c = -1;
    calcSizes (v);
    findCentroid (v, sz[v]);
    //minLen.clear();
    //FOR(i, 0, k) minLen[i] = -1;
    minLen[0] = 0;
    changed.clear();

    for (auto pp : adj[c]) {
        int u = pp.f;
        ll w = pp.s;
        if (vis[u]) continue;
        //paths.clear();
        getPaths(u, w, 1, c);
//cout << " paths from v = " << v << " trrough u = " << u << endl;
        getPaths2(u,w,1,c);
    }

    for (int x : changed)
        minLen[x] = -1;

    vis[c] = true;
    for (auto pp : adj[c]) {
        int u = pp.f;
      //  ll w = pp.s;
        if (vis[u]) continue;
        trav(u);
    }

}

int best_path(int N, int K, int H[][2], int L[])
{
    n = N;
    k = K;
    FOR(i, 0, n-2) {
        int u = H[i][0], v = H[i][1], w = L[i];
        u++;
        v++;
        adj[u].pb({v, w});
        adj[v].pb({u, w});
    }

    FOR(i, 1, k) minLen[i] = -1;
    trav (1);

    return ans;
}

/*
2 2
0 1 1
-1


*/

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