oj.uz

답안 #1047962

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1047962 2024-08-07T18:54:49 Z manhlinh1501 경주 (Race) (IOI11_race) C++17
0 / 100
 114 ms 262144 KB 
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
using pii = pair<int, int>;
const int MAXN = 2e5 + 5;
const int oo32 = 2e9;

int N, K;
vector<pii> adj[MAXN];
map<int, int> res[MAXN];
int ans = oo32;

void DFS(int u, const int N, const int K, i64 c = 0, int depth = 0, int p = -1) {
    res[u][c] = depth;
    for(auto [v, w] : adj[u]) {
        if(v == p) continue;
        DFS(v, c + w, depth + 1, u);
        if(res[u].size() < res[v].size()) swap(res[u], res[v]);
        for(auto [x, y] : res[v]) {
            if(res[u].find(c + K - (x - c)) != res[u].end())
                ans = min(ans, y + res[u][c + K - (x - c)] - 2 * depth);
        }
        for(auto [x, y] : res[v]) {
            if(res[u].find(x) != res[u].end())
                res[u][x] = min(res[u][x], y);
            else res[u][x] = y;
        }
    }
}

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

Subtask #1
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 114 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 114 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 114 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 114 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -