제출 #681421

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
681421		phoebe	경주 (Race) (IOI11_race)	C++17	100 / 100	2480 ms	40844 KiB

race

#include <bits/stdc++.h>
#include "race.h"
using namespace std;
 
// #define int long long
#define ll long long
#define pii pair<int, int>
#define F first
#define S second
#define PB push_back
#define ALL(x) x.begin(), x.end()
#define FOR(i, n) for (int i = 0; i < n; i++)
#define NYOOM ios::sync_with_stdio(0); cin.tie(0);
#define endl '\n'
const int INF = 1e9 + 7;
const ll LLINF = 1ll<<60;
 
const int maxn = 2e5 + 10;
int n, k, sz[maxn];
vector<pair<pii, int>> adj[maxn];
map<int, int> small, large;
set<int> deleted;
 
void init(int v, int p){
    sz[v] = 1;
    for (auto x : adj[v]){
        int u = x.F.F, w = x.F.S, i = x.S;
        if (deleted.count(i)) continue;
        if (u == p) continue;
        init(u, v); sz[v] += sz[u];
    }
}
 
int get_centroid(int v, int p, int pog){
    for (auto x : adj[v]){
        int u = x.F.F, w = x.F.S, i = x.S;
        if (deleted.count(i)) continue;
        if (u == p) continue;
        if (sz[u] * 2 > pog) return get_centroid(u, v, pog);
    }
    return v;
}
 
void dfs(int v, int p, int h, int cnt){
    if (small.count(h)) small[h] = min(small[h], cnt);
    else small[h] = cnt;
    for (auto x : adj[v]){
        int u = x.F.F, w = x.F.S, i = x.S;
        if (deleted.count(i)) continue;
        if (u == p) continue;
        dfs(u, v, h + w, cnt + 1);
    }
}
 
int solve(int v){
    init(v, v);
    v = get_centroid(v, -1, sz[v]);
    int re = INF;
    large.clear();
    small.clear();
    large[0] = 0;
    for (auto x : adj[v]){
        int u = x.F.F, w = x.F.S, i = x.S;
        if (deleted.count(i)) continue;
        dfs(u, v, w, 1);
        for (auto bruh : small){
            if (large.count(k - bruh.F)){
                re = min(re, bruh.S + large[k - bruh.F]);
            }
        }
        for (auto bruh : small){
            if (large.count(bruh.F)) large[bruh.F] = min(large[bruh.F], bruh.S);
            else large[bruh.F] = bruh.S;
        }
        small.clear();
    }
    for (auto x : adj[v]){
        int u = x.F.F, w = x.F.S, i = x.S;
        if (deleted.count(i)) continue;
        deleted.insert(i);
        re = min(re, solve(u));
    }
    return re;
}
 
int best_path(int N, int K, int h[][2], int l[]){
    n = N, k = K;
    FOR(i, n - 1){
        adj[h[i][0]].PB({{h[i][1], l[i]}, i});
        adj[h[i][1]].PB({{h[i][0], l[i]}, i});
    }
    int re = solve(0);
    return (re == INF ? -1 : re);
}

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

race.cpp: In function 'void init(int, int)':
race.cpp:27:24: warning: unused variable 'w' [-Wunused-variable]
   27 |         int u = x.F.F, w = x.F.S, i = x.S;
      |                        ^
race.cpp: In function 'int get_centroid(int, int, int)':
race.cpp:36:24: warning: unused variable 'w' [-Wunused-variable]
   36 |         int u = x.F.F, w = x.F.S, i = x.S;
      |                        ^
race.cpp: In function 'int solve(int)':
race.cpp:78:24: warning: unused variable 'w' [-Wunused-variable]
   78 |         int u = x.F.F, w = x.F.S, i = x.S;
      |                        ^

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