제출 #501009

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

race

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

const int N = 2e5 + 10;
const int INF = 1e9 + 7;

vector <pair <int, int>> adj[N];
int sz[N];
bool visited[N];
map <long long, int> mp;
int ans = INF;

int find_size(int u, int p) {
    sz[u] = 1;
    for(auto [v, w] : adj[u]) {
        if(v == p || visited[v]) {
            continue;
        }

        sz[u] += find_size(v, u);
    }
    return sz[u];
}

int find_centroid(int u, int p, int n) {
    for(auto [v, w] : adj[u]) {
        if(v == p || visited[v]) {
            continue;
        }

        if(sz[v] > n / 2) {
            return find_centroid(v, u, n);
        }
    }
    return u;
}

void dfs(int u, int p, long long total, bool state, int depth, int K) {
    if(state) {
        if(mp.count(total)) {
            mp[total] = min(mp[total], depth);
        }
        else {
            mp[total] = depth;
        }
    }
    else {
        if(mp.count(K - total)) {
            ans = min(ans, depth + mp[K - total]);
        }
    }

    for(auto [v, w] : adj[u]) {
        if(v == p || visited[v]) {
            continue;
        }

        dfs(v, u, total + w, state, depth + 1, K);
    }
}

void centroid(int u, int K) {
    int c = find_centroid(u, -1, find_size(u, -1));
    visited[c] = 1;

    mp.clear();
    for(auto [v, w] : adj[c]) {
        if(visited[v]) {
            continue;
        }

        dfs(v, -1, w, 0, 1, K);
        dfs(v, -1, w, 1, 1, K);
    }

    for(auto [v, w] : adj[c]) {
        if(visited[v]) {
            continue;
        }

        centroid(v, K);
    }
}

int best_path(int N, int K, int H[][2], int L[]) {
    for(int i = 0; i < N - 1; i++) {
        H[i][0]++, H[i][1]++;
        adj[H[i][0]].emplace_back(H[i][1], L[i]);
        adj[H[i][1]].emplace_back(H[i][0], L[i]);
    }

    centroid(1, K);
    
    if(ans == INF) {
        ans = -1;
    }
    return ans;
}

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