Submission #1196821

#	Time	Username	Problem	Language	Result	Execution time	Memory
1196821		reginox	Race (IOI11_race)	C++20	100 / 100	387 ms	103308 KiB

race

#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define all(v) begin(v), end(v)
#define pi pair<int, int>
#define vi vector<int>
using namespace std;
const int N = 2e5+3;
vector<pair<int,ll>> g[N];
map<ll, int> mp[N];
int res = 1e9;
int n, k;
ll dist[N]; int dep[N];

void pre(int u, int p, int len, int h){
    dist[u] = len;
    dep[u] = h;
    for(auto [v,w]:g[u]){
        if(v == p) continue;
        pre(v, u, len + w, h+1);
    }
}

void dfs(int u, int p){
    mp[u][dist[u]] = dep[u];
    for(auto [v,w]:g[u]){
        if(v == p) continue;
        dfs(v, u);
        if(mp[u].size() < mp[v].size()) swap(mp[u], mp[v]);
        for(auto [x,y]:mp[v]){
            if(mp[u].find(k + 2 * dist[u] - x) != mp[u].end())
                res = min(res, mp[u][k+2*dist[u] - x] + y - 2*dep[u]);
        }
        for(auto [x,y]:mp[v]){
            if(mp[u].find(x) != mp[u].end()){
                mp[u][x] = min(mp[u][x], y);
            }
            else{
                mp[u][x] = y;
            }
        }
    }
}

int best_path(int N, int K, int H[][2], int L[]){
    n = N;
    k = K;
    for(int i = 0; i < N-1; i++){
        g[H[i][0]+1].push_back({H[i][1]+1, L[i]});
        g[H[i][1]+1].push_back({H[i][0]+1, L[i]});
    }
    pre(1, 0, 0, 0);
    dfs(1, 0);
    return (res == 1e9? -1:res);
}

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