oj.uz

답안 #838868

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
838868 2023-08-28T02:53:06 Z Shreyan_Paliwal 경주 (Race) (IOI11_race) C++17
0 / 100
 8 ms 15956 KB 
// #pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;

// #define int long long

template<int SZ> struct Tree {
    int n;
    vector<pair<int,int>> adj[SZ];
    void init(int N, int H[][2], int L[]) {
        n = N;
        for (int i = 0; i < n-1; i++) {
            int a, b, c; cin >> a >> b >> c;
            adj[H[i][0]].push_back({H[i][1], L[i]});
            adj[H[i][1]].push_back({H[i][0], L[i]});
        }
    }
};

const int maxn = 200000;

int n, k;
int sz[maxn], dpth[maxn], ldpth[maxn];
Tree<maxn> tree;
unordered_map<int,int> m[maxn];

int ans = INT_MAX;

int dfs(int nd, int par, int l) {
    sz[nd] = 1, dpth[nd] = dpth[par] + 1; ldpth[nd] = l;
    for (auto i : tree.adj[nd])
        if (i.first != par)
            sz[nd] += dfs(i.first, nd, l + i.second);
    return sz[nd];
}

inline int mget(int nd, int dist) {
    // dist to find = ldist[nd] + dist;
    dist += ldpth[nd];
    if (m[nd].find(dist) == m[nd].end()) return INT_MAX;
    return m[nd][dist];
}

inline void upd_min(int nd, int k, int v) {
    if (m[nd].find(k) == m[nd].end()) {m[nd][k] = v; return; }
    // cout << "Y " << nd << ' ' << k << ' ' << (m[nd].find(k) == m[nd].end()) << ' ' << m[nd][k] << ' ';
    m[nd][k] = min(m[nd][k], v);
    // cout << m[nd][k] << endl;
}

void msl(int nd, int par) {

    for (auto i : tree.adj[nd])
        if (i.first != par)
            msl(i.first, nd);

    int hch = -1, hb = -1;
    for (auto i : tree.adj[nd])
        if (i.first != par)
            if (hch == -1 || hb < sz[i.first])
                hch = i.first, hb = sz[i.first];
    // cout << "Z " << nd << ' ' << (hch == -1) << endl;
    if (hch == -1) {m[nd][ldpth[nd]] = dpth[nd];
    // cout << "---------" << endl << nd << endl;
    // cout << "X ";
    // for (auto i : m[nd]) cout << i.first << ' ' << i.second << ' ';
    // cout << endl;
    return;}
    // cout << "----" << endl;

    swap(m[nd], m[hch]);

    // cout << nd << endl;
    for (auto i : tree.adj[nd])
        if (i.first != par && i.first != hch)
            for (auto j : m[i.first]) {
                // cout << j.first << ' ' << j.second << endl;
                // (dist[i], dpth[i]) --> (dist[i] - dist[nd], dpth[i] - dpth[nd])
                int val = mget(nd, k - (j.first - ldpth[nd]));
                if (val != INT_MAX)
                    ans = min(ans, j.second + mget(nd, k - (j.first - ldpth[nd])) - 2*dpth[nd]);
                // if (val != INT_MAX)
                //     cout << nd << ' ' << j.first << ' ' << j.second << ' ' << j.second + mget(nd, k - (j.first - ldpth[nd])) - 2*dpth[nd] << endl;
                upd_min(nd, j.first, j.second);
            }

    // cout << nd << ' ' << mget(nd, k) - dpth[nd] << endl;
    // cout << "X ";
    // for (auto i : m[nd]) cout << i.first << ' ' << i.second << ' ';
    // cout << endl;
    ans = min(ans, mget(nd, k) - dpth[nd]);
    upd_min(nd, ldpth[nd], dpth[nd]);
}

int best_path(int N, int K, int H[][2], int L[]) {
    n = N, k = K;
    tree.init(n, H, L);
    dfs(0, 0, 0);
    msl(0, 0);
    return ans;
}

// #define LOCAL
// #define CODEFORCES
// signed main() {
//     #ifndef LOCAL
//     cin.tie(nullptr) -> ios::sync_with_stdio(false);
//     #endif
//     #ifdef LOCAL
//     freopen("main.in", "r", stdin);
//     #endif
//     int t; 
//     #ifdef CODEFORCES
//     cin >> t;
//     #endif
//     #ifndef CODEFORCES
//     t=1;
//     #endif
//     while(t--) solve();
//     return 0;
// }

Subtask #1
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 15956 KB Output is correct
2 Correct 7 ms 15932 KB Output is correct
3 Incorrect 7 ms 15956 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 15956 KB Output is correct
2 Correct 7 ms 15932 KB Output is correct
3 Incorrect 7 ms 15956 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 15956 KB Output is correct
2 Correct 7 ms 15932 KB Output is correct
3 Incorrect 7 ms 15956 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 15956 KB Output is correct
2 Correct 7 ms 15932 KB Output is correct
3 Incorrect 7 ms 15956 KB Output isn't correct
4 Halted 0 ms 0 KB -