제출 #1231871

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1231871		AMel0n	Race (IOI11_race)	C++20	100 / 100	507 ms	43132 KiB

race

// I wonder how much faster it is (cos this one passes on train https://train.nzoi.org.nz/submissions/166506 while my other OJ AC doesn't)
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
#define FOR(i,N) for(ll i = 0; i < N; i++)
#define all(x) (x).begin(), (x).end()
#define F first
#define S second


// #include "race.h"
// centroid decomp & dp => O(N * log^2 N)

int N, K, res = INT_MAX;
vector<vector<pair<int,int>>> adj;
vector<int> sz;
vector<bool> del;

int dfsSZ(int n, int p) {
    sz[n] = 1;
    for(auto [c, l]: adj[n]) {
        if (c == p || del[c]) continue;
        sz[n] += dfsSZ(c, n);
    }
    return sz[n];
}

int dfsCEN(int n, int p, int treeSZ) {
    for(auto [c, l]: adj[n]) {
        if (c == p || del[c] || sz[c] * 2 <= treeSZ) continue;
        return dfsCEN(c, n, treeSZ);
    }
    return n;
}

void solve(int n, int p, int dist, int dep, unordered_map<int,int> &dp) {
    if (dist > K) return ;
    if (dp.find(K-dist) != dp.end()) res = min(res, dp[K-dist] + dep);
    if (dist == K) {res = min(res, dep); return ;}
    for(auto [c, l]: adj[n]) {
        if (c == p || del[c]) continue;
        solve(c, n, dist+l, dep+1, dp);
    }
}
void solve2(int n, int p, int dist, int dep, unordered_map<int,int> &dp) {
    if (dp.find(dist) == dp.end() || dp[dist] > dep) dp[dist] = dep;
    if (dist >= K) return ;
    for(auto [c, l]: adj[n]) {
        if (c == p || del[c]) continue;
        solve2(c, n, dist+l, dep+1, dp);
    }
}

void build(int n) {
    int cen = dfsCEN(n, n, dfsSZ(n, n));

    // for every centroid, there will be at most N' values (where N' = the number of nodes in the centroid)
    // subset sum dp - in the solve on line 39 and solve2 on line 47
    unordered_map<int,int> dp;
    for(auto [c, l]: adj[cen]) {
        if (del[c]) continue;
        solve(c, cen, l, 1, dp);
        solve2(c, cen, l, 1, dp);
    }

    del[cen] = true;
    for(auto [c, l]: adj[cen]) {
        if (del[c]) continue;
        build(c); 
    }
}

int best_path(int N, int K, int H[][2], int L[]) {
    ::N = N, ::K = K;
    adj.resize(N), sz.resize(N), del.resize(N);
    FOR(i, N-1) {
        adj[H[i][0]].push_back({H[i][1], L[i]});
        adj[H[i][1]].push_back({H[i][0], L[i]});
    }
    build(0);
    return (res == INT_MAX ? -1 : res);
}

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