oj.uz

Submission #1047966

# Submission time Handle Problem Language Result Execution time Memory
1047966 2024-08-07T19:07:05 Z manhlinh1501 Race (IOI11_race) C++17
0 / 100
 3 ms 18012 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;
#define sz(a) (int)a.size()
int N, K;
vector<pii> adj[MAXN];
map<i64, int> dp[MAXN];
int ans = oo32;

template<class T> bool umin(T& a, const T& b) {
    return b < a ? a = b, 1 : 0;
}

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

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

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 18012 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 18012 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 18012 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 18012 KB Output isn't correct
2 Halted 0 ms 0 KB -