제출 #343157

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
343157		Aldas25	경주 (Race) (IOI11_race)	C++14	43 / 100	3096 ms	54112 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];

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});
}

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;

    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;
        for (auto p : paths) {
            int dep = p.f;
            ll len = p.s;
            //cout << "   path dep = " << dep << " len = " << len << endl;
            if (len > k) continue;
            else {
                int remLen = k - len;
                if (minLen[remLen] != -1) {
                    int dep2 = minLen[remLen] + dep;
                    if (ans == -1) ans = dep2;
                    else ans = min(ans, dep2);
                }
            }
        }

        for (auto p : paths) {
            int dep = p.f;
            ll len = p.s;
            if (len >= k) continue;
            else {
                if (minLen[len] == -1) minLen[len] = dep;
                else minLen[len] = min(minLen[len], dep);
            }
        }
    }

    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});
    }

    trav (1);

    return ans;
}

/*
2 2
0 1 1
-1


*/

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