oj.uz

답안 #1097648

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1097648 2024-10-07T19:46:50 Z SiddharthJoshi6263 경주 (Race) (IOI11_race) C++17
0 / 100
 1 ms 344 KB 
#include <bits/stdc++.h>

using namespace std;

// #ifdef ONLINE_JUDGE
// #define debug(...)
// #else
// #include "debug.h"
// #endif

#define f first
#define s second
#define pb push_back
#define all(x) x.begin(), x.end()
#define sz(x) (long long)(x).size()
#define pii pair<long long, long long>

long long ANS = INT_MAX;

void dfs_sze(long long u, long long par, vector<vector<pii>> &adj, vector<long long> &sze, vector<long long> &len, vector<long long> &depth) {
    sze[u] = 1;
    for (auto v : adj[u]) {
        if (v.f != par) {
            dfs_sze(v.f, u, adj, sze, len, depth);
            sze[u] += sze[v.f];
            len[v.f] = len[u] + v.s;
            depth[v.f] = depth[u] + 1;
        }
    }
}

void small_to_large_merging(long long K, long long u, long long par, vector<long long> &sze, vector<long long> &len, vector<long long> &depth, vector<vector<pii>> &adj, vector<multiset<pii>> &sets) {
    long long big = -1, big_wt = 0;
    for (auto v : adj[u]) {
        if (v.f != par) {
            if (big == -1 || sze[big] < sze[v.f]) {
                big = v.f;
                big_wt = v.s;
            }
        }
    }
    if (big == -1) {
        return;
    }
    small_to_large_merging(K, big, u, sze, len, depth, adj, sets);
    vector<pii> smalls1, smalls2;
    for (auto x : adj[u]) {
        if (x.f != par && x.f != big) {
            small_to_large_merging(K, x.f, u, sze, len, depth, adj, sets);
            long long edge_wt = x.s;
            for (auto y : sets[x.f]) {
                smalls1.pb({y.f, y.s});
                long long act_len = y.f - len[x.f] + edge_wt + big_wt;
                long long act_dep = y.s - depth[x.f] + 2;
                long long find_len = K - act_len;
                if (find_len <= 0)continue;
                long long search = find_len + len[big];
                pii finds = {search, -1ll};
                auto vals = sets[big].lower_bound(finds);
                if (vals != sets[big].end()) {
                    if (vals->f == search) {
                        ANS = min(ANS, act_dep + vals->s - depth[big]);
                    }
                }
            }
            for (auto y : sets[x.f]) {
                smalls2.pb({y.f + edge_wt - big_wt, y.s});
                sets[big].insert({y.f + edge_wt - big_wt, y.s});
            }
        }
    }
    for (auto x : smalls1) {
        sets[big].insert(x);
    }
    for (auto x : smalls2) {
        sets[big].erase(sets[big].find(x));
    }
    sets[u].swap(sets[big]);
    sets[u].insert({len[u], depth[u]});
    pii finds = {K, -1ll};
    auto vals = sets[u].lower_bound(finds);
    if (vals != sets[u].end()) {
        if (vals->f == K + depth[u]) {
            ANS = min(ANS, vals->s - depth[u]);
        }
    }
}

int best_path(int N, int k, int H[][2], int L[]) {
    long long n = N, K = k;
    vector<vector<pii>> adj(n);
    for (long long i = 0; i < n - 1; i++) {
        adj[H[i][0]].pb({H[i][1], L[i]});
        adj[H[i][1]].pb({H[i][0], L[i]});
    }
    vector<long long> sze(n, 0);
    vector<long long> len(n, 0);
    vector<long long> depth(n, 0);
    dfs_sze(0, -1, adj, sze, len, depth);
    vector<multiset<pii>> sets(n);
    for (long long i = 0; i < n; i++) {
        sets[i].insert({len[i], depth[i]});
    }
    small_to_large_merging(K, 0, -1, sze, len, depth, adj, sets);
    if (ANS == INT_MAX) {
        return -1;
    }
    return ANS;
}


// void solve() {
//     long long n, K;
//     cin >> n >> K;
//     long long H[n - 1][2];
//     long long L[n - 1];
//     for (long long i = 0; i < n - 1; i++) {
//         cin >> H[i][0] >> H[i][1];
//     }
//     for (long long i = 0; i < n - 1; i++) {
//         cin >> L[i];
//     }
//     cout << best_path(n, K, H, L) << endl;
// }

// signed main() {
//     ios_base::sync_with_stdio(false);
//     cin.tie(NULL);
//     cout.tie(NULL);
//     long long zz = 1;
//     // cin >> zz;
//     for (long long i = 1; i <= zz; i++) {
//         // cout << "Case #" << i << ": ";
//         solve();
//     }
//     return 0;
// }

Subtask #1
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -