Submission #789097

#	Time	Username	Problem	Language	Result	Execution time	Memory
789097		diobrando97	Race (IOI11_race)	C++17	0 / 100	7 ms	11992 KiB

race

    #include <bits/stdc++.h>
    #pragma GCC optimize(3)
    #define ll long long
    #define pii pair<int, int>
    #define pll pair<long long, long long>
    #define F first
    #define S second
    #define endl '\n'
    using namespace std;
    const int inf = 0x3f3f3f3f;
    const int mod = 1e9 + 7;
    const int N = 2e5 + 5;

    double startTime = clock();
    double getCurrentTime() {
        return (double)(clock() - startTime) / CLOCKS_PER_SEC;
    }

    int n, k;
    int ans = inf;
    int tot = 0, cur = 0;
    array<int, 3> dis[N];
    multiset<int> st[N];

    struct CD{
        int n;
        vector<vector<pii>> g;
        vector<int> par, sz;
        vector<bool> vis;
        
        CD(){}
        CD(int n){
            init(n);
        }

        void init(int n){
            this->n = n;
            g.assign(n+1, {});
            par.assign(n+1, 0);
            sz.assign(n+1, 0);
            vis.assign(n+1, 0);
        }
        
        void addEdge(int x, int y, int w){
            g[x].push_back({y, w});
            g[y].push_back({x, w});
        }
        
        void dfs(int i, int f){
            sz[i] = 1;
            for(auto [j, w] : g[i]){
                if(j == f || vis[j]) continue;
                dfs(j, i);
                sz[i] += sz[j];
            }
        }

        int getCentroid(int i, int f, int n){
            for(auto [j, w] : g[i]){
                if(j == f || vis[j]) continue;
                if(sz[j] * 2 > n) return getCentroid(j, i, n);
            }
            return i;
        }
        
        void dfs2(int i, int f, int w, int len, int mark){
            if(w > k) return;
            dis[++tot] = {w, len, mark};
            for(auto [j, wj] : g[i]){
                if(j == f || vis[j]) continue;
                dfs2(j, i, w+wj, len+1, mark);
            }
            
        }

        void work(int i, int f = 0){
            dfs(i, f);
            int cen = getCentroid(i, f, sz[i]);
            vis[cen] = 1;
            par[cen] = f;

            tot = cur = 0;
            for(auto [j, w] : g[cen]){
                if(j == f || vis[j]) continue;
                dfs2(j, i, w, 1, ++cur);
            }

            st[0] = {0};
            for(int j=1; j<=tot; j++){
                st[dis[j][0]].insert(dis[j][1]);
            }
            int x = 1, y = 1;
            for(int j=1; j<=cur; j++){
                while(x <= tot && dis[x][2] == j){
                    st[dis[x][0]].erase(st[dis[x][0]].find(dis[x][1]));
                    x++;
                }
                while(y <= tot && dis[y][2] == j){
                    int tar = k - dis[y][0];
                    if(tar >= 0 && tar <= k && !st[tar].empty()){
                        ans = min(ans, dis[y][1] + *st[tar].begin());
                    }
                    y++;
                }
            }
            
            for(auto [j, w] : g[cen]){
                if(vis[j]) continue;
                work(j, cen);
            }
        }
    };

    int best_path(int N, int K, int h[][2], int l[]) {
        n = N; k = K;
        CD cent(n);
        for (int i = 0; i < n - 1; i++) {
            int x = h[i][0] + 1, y = h[i][1] + 1, w = l[i];
            cent.addEdge(x, y, w);
        }
        memset(dis, 0, sizeof dis);
        for(int i=1; i<=k; i++) st[i].clear();

        cent.work(1, 0);
        return (ans == inf ? -1 : ans);
        // cout << (ans == inf ? -1 : ans) << endl;
    }

    // void solve(){
    //     cin >> n >> k;
    //     CD cent(n);
    //     for(int i=1; i<n; i++){
    //         int x, y, w; cin >> x >> y >> w;
    //         x++; y++;
    //         cent.addEdge(x, y, w);
    //     }
        
    //     memset(dis, 0, sizeof dis);
    //     for(int i=1; i<=n; i++) st[i].clear();

    //     cent.work(1, 0);
    //     cout << (ans == inf ? -1 : ans) << endl;
    // }


    // int main(){
    //     ios::sync_with_stdio(0); cin.tie(0);
    //     freopen("input.txt", "r", stdin);
    //     freopen("output.txt", "w", stdout);

    //     int t = 1;
    //     //cin >> t;
    //     while(t--)
    //     solve();

    //     return 0;
    // }

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