Submission #1130453

#	Time	Username	Problem	Language	Result	Execution time	Memory
1130453		akzytr	Race (IOI11_race)	C++17	43 / 100	2200 ms	73000 KiB

race

#include <bits/stdc++.h>
#define ve vector
#define ar array 
#define pb push_back
#define ins insert

#define endl '\n'
#define ll long long
using namespace std;

const int MXN = 2e5+5;
int K;
ve<pair<int, ll>> adj[MXN];

int dfs1(int x, int p, int need){
    if(need == 0){
        return 1;
    }
    if(need < 0){
        return 1e9;
    }
    int ans = 1e9;
    for(auto [i, c] : adj[x]){
        if(i != p){
            ans = min(ans, 1 + dfs1(i, x, need-c));
        }
    }
    return ans;
}
int dfs2(int x, int p){
    int ans = 1e9;
    for(auto [i, c] : adj[x]){
        if(i != p){
            ans = min(ans, dfs1(i, x, K-c));
        }
    }
    return ans;
}


map<int, int> pos[MXN];
int dfs3(int x, int p){
    int ans = 1e8;
    pos[x][0] = 0;

    for(auto [i, c] : adj[x]){
        if(i != p){
            // if(c > K){
            //     continue;
            // }
            ans = min(ans, dfs3(i, x));
            for(int j = c; j <= K; j++){
                if(pos[i].count(j-c) && pos[x].count(K-j)){
                    ans = min(ans, pos[i][j-c] + pos[x][K-j] + 1);
                }
            }
            for(int j = 0; j+c <= K; j++){
                if(pos[i].count(j)){
                    if(pos[x].count(j+c)){
                        pos[x][j+c] = min(pos[x][j+c], pos[i][j] + 1);   
                    }
                    else{
                        pos[x][j+c] = pos[i][j] + 1;
                    }
                }
            }

            for(int j = 0; j+c <= K; j++){
                if(pos[i].count(j)){
                    pos[i].erase(j);
                }
            }

        }
    }

    return ans;

}

int best_path(int N, int k, int H[][2], int L[]){
    K = k;
    for(int 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]});
    }
    if(K <= 100){
        int ans = dfs3(0, -1);
        if(ans == 1e8){
            ans = -1;
        }
        return ans;
    }
    else if(N <= 1000){
        int ans = 1e9;
        for(int i = 0; i < N; i++){
            ans = min(ans, dfs2(i, -1));
        }
        if(ans == 1e9){
            return -1;
        }
        else{
            return ans;
        }
    }
    return -1;
    
}

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