제출 #433971

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
433971		illyakr	경주 (Race) (IOI11_race)	C++14	0 / 100	4 ms	4940 KiB

race

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

vector<pair<int, int> > g[201010];
int sz[201010];
bool del[201010];
void rcn(int v, int pred) {
    sz[v] = 1;
    for (auto [to, c] : g[v]) {
        if (to == pred || del[to]) continue;
        rcn(to, v);
        sz[v] += sz[to];
    }
}
int centroid(int v, int pred, int N) {
    for (auto [to, c] : g[v]) {
        if (to == pred || del[to])continue;
        if (sz[to] > N / 2)
            return centroid(to, v, N);
    }
    return v;
}
int Kur;
int have[1010101];
int res = 1010101010;
void dfs(int v, int pred, int sum, int depth) {
    if (have[Kur - sum] != -1)
        res = min(res, have[Kur - sum] + depth);
    for (auto [to, c] : g[v]) {
        if (to == pred || del[to] || sum + c > Kur)continue;
        dfs(to, v, sum + c, depth + 1);
    }
}
void put(int v, int pred, int sum, int depth) {
    if (have[sum] != -1)
        have[sum] = min(have[sum], depth);
    else
        have[sum] = depth;
    for (auto [to, c] : g[v]) {
        if (to == pred || del[to] || sum + c > Kur)continue;
        put(to, v, sum + c, depth + 1);
    }
}
void erc(int v, int pred, int sum, int depth) {
    have[sum] = -1;
    for (auto [to, c] : g[v]) {
        if (to == pred || del[to] || sum + c > Kur)continue;
        erc(to, v, sum + c, depth + 1);
    }
}

void decomposition(int v) {
    del[v] = true;
    rcn(v, v);
    for (auto [to, c] : g[v]) {
        if (c > Kur)continue;
        erc(to, v, c, 1);
    }
    have[0] = 0;
    for (auto [to, c] : g[v]) {
        if (del[to] || c > Kur)continue;
        dfs(to, v, c, 1);
        put(to, v, c, 1);
    }
    for (auto [to, c] : g[v]) {
        if (del[to])continue;
        decomposition(centroid(to, v, sz[to]));
    }

}

int best_path(int N, int K, int H[][2], int L[]) {
    for (int i = 0; i < N - 1; i++) {
        g[H[i][0] + 1].push_back({H[i][1] + 1, L[i]});
        g[H[i][1] + 1].push_back({H[i][0] + 1, L[i]});
    }
    Kur = K;
    rcn(1, 1);
    decomposition(centroid(1, 1, N));
//    cout << centroid(1, 1, N) << " !!" << endl;

    if (res == 1010101010)return -1;
    return res;
}

/**
3 3
0 1 1
1 2 1
-1

11 12
0 1 3
0 2 4
2 3 5
3 4 4
4 5 6
0 6 3
6 7 2
6 8 5
8 9 6
8 10 7
2
*/

컴파일 시 표준 에러 (stderr) 메시지

race.cpp: In function 'void rcn(int, int)':
race.cpp:10:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   10 |     for (auto [to, c] : g[v]) {
      |               ^
race.cpp: In function 'int centroid(int, int, int)':
race.cpp:17:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   17 |     for (auto [to, c] : g[v]) {
      |               ^
race.cpp: In function 'void dfs(int, int, int, int)':
race.cpp:30:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   30 |     for (auto [to, c] : g[v]) {
      |               ^
race.cpp: In function 'void put(int, int, int, int)':
race.cpp:40:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   40 |     for (auto [to, c] : g[v]) {
      |               ^
race.cpp: In function 'void erc(int, int, int, int)':
race.cpp:47:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   47 |     for (auto [to, c] : g[v]) {
      |               ^
race.cpp: In function 'void decomposition(int)':
race.cpp:56:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   56 |     for (auto [to, c] : g[v]) {
      |               ^
race.cpp:61:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   61 |     for (auto [to, c] : g[v]) {
      |               ^
race.cpp:66:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   66 |     for (auto [to, c] : g[v]) {
      |               ^

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