Submission #1162470

#	Time	Username	Problem	Language	Result	Execution time	Memory
1162470		CrabCNH	Race (IOI11_race)	C++20	0 / 100	22 ms	47192 KiB

race

#include <bits/stdc++.h>

#define task   "brianthecrab"

#define int    long long
#define pii    pair <int, int>
#define fi     first
#define se     second
#define szf    sizeof
#define sz(s)  (int)((s).size())
#define all(v) (v).begin(), (v).end()

using namespace std;

template <class T> void mini (T &t, T f) {if (t > f) t = f;}
template <class T> void maxi (T &t, T f) {if (t < f) t = f;}

const int inf = 1e18 + 7;
const int mod = 1e9 + 7;

int n, k;
int tt;

struct CD {
    int sz[1000005], edgecnt[1000005], exist[1000005];
    set <pii> G[1000005];
    
    // get sz
    
    int dfs (int u, int p) {
        sz[u] = 1;
        for (auto [v, dis] : G[u]) {
            if (v == p) {
                continue;
            }
            sz[u] += dfs (v, u);
        }
        return sz[u];
    }
    
    // find centroid
        
    int centroid (int u, int p, int nn) {
        for (auto [v, dis] : G[u]) {
            if (v == p) {
                continue;
            }
            if (sz[v] > nn / 2) {
                return centroid (v, u, nn);
            }
        }
        return u;
    }
    
    // exist kiem tra xem da co gia tri want o trong cac cay con goc centroid da xet chua
    // neu co cap nhat lai ans
    // neu ma gia tri d van nho hon k thi ta se push no vao 1 vector
    // khi do xet tiep cac dinh ke canh hien tai va roi xet tiep den cay goc tiep theo
    // cap nhat lai gia tri ans khi xet duoc con tot nhat o 1 cay con nao day
        
    int dfs2 (int u, int p, int d, int cnt, int t, vector <pii> &vv) {
        int want = k - d;
        int ans = inf;
        if (want >= 0 && exist[want] == t) {
            mini (ans, cnt + edgecnt[want]);
        }
        if (d <= k) {
            vv.push_back ({d, cnt});
            for (auto [v, dis] : G[u]) {
                if (v == p) {
                    continue;
                }
                int cur = dfs2 (v, u, d + dis, cnt + 1, t, vv);
                mini (ans, cur);
            }
        }
        return ans;
    }
    
    /*
    Solve(u):
    ans = inf
    for v là con u:
        ans = min(ans, Solve(v))
    DFS từ u để tính khoảng cách và số cạnh đã sử dụng trong thành phần của u
    Sử dụng DFS khác để tính kết quả, trong khi sử dụng một mảnh để truy vết các đường đi thỏa mãn bắt đầu từ
    u và số cạnh cần dùng ít nhất
    cập nhật ans từ hàm DFS trước
    return ans
    */
    
    int sol (int u, int p) {
        int nn = dfs (u, p);
        int c = centroid (u, p, nn);
        int ans = inf;
        int t = ++tt;
        exist[0] = t;
        edgecnt[0] = 0;
        for (auto [v, dis] : G[c]) {
            vector <pii> tmp;
            int cur = dfs2 (v, c, dis, 1, t, tmp);
            mini (ans, cur);
            for (auto [v1, dis1] : tmp) {
                if (exist[v1] != t || (exist[v1] == t && edgecnt[v1] > dis1)) {
                    exist[v1] = t;
                    edgecnt[v1] = dis1;
                }
            }
        }
        vector <pii> tmp (G[c].begin (), G[c].end ());
        for (auto [v, dis] : tmp) {
            G[c].erase ({v, dis});
            G[v].erase ({c, dis});
            int cur = sol (v, c);
            mini (ans, cur);
        }
        return ans;
    }
} T;

int32_t best_path(int32_t N, int32_t K, int32_t H[][2], int32_t L[]){
    n = N, k = K;
    for (int i = 1; i <= n - 1; i ++) {
        int u = H[i][0], v = H[i][1], w = L[i];
        T.G[u].insert ({v, w});
        T.G[v].insert ({u, w});
    }
    tt = 0;
    int ans = T.sol (0, -1);
    return (ans == inf ? - 1 : ans);
}
// hmvncvdqdela

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