Submission #1141272

#	Time	Username	Problem	Language	Result	Execution time	Memory
1141272		TahirAliyev	Race (IOI11_race)	C++17	100 / 100	345 ms	90364 KiB

race

#include "race.h"
#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define pii pair<ll, ll>
#define oo 1e9

const int MAX = 2e5 + 5;

vector<pii> g[MAX];
int n, k;

map<ll, int> mp[MAX];

int ans = oo;

void dfs(int node, int p, ll d, int h){
    for(pii to : g[node]){
        if(to.first == p) continue;
        dfs(to.first, node, d + to.second, h + 1);
        if(mp[to.first].size() > mp[node].size()){
            swap(mp[node], mp[to.first]);
        }
    }
    for(pii to : g[node]){
        if(to.first == p) continue;
        for(auto a : mp[to.first]){
            if(!a.second) continue;
            ll need = d + (k - (a.first - d));
            if(need <= d || mp[node].find(need) == mp[node].end()) continue;
            ans = min(ans, (a.second - h) + (mp[node][need] - h));
        }
        for(auto a : mp[to.first]){
            if(!a.second) continue;
            if(mp[node].find(a.first) == mp[node].end()){
                mp[node][a.first] = a.second;
            }
            else{
                mp[node][a.first] = min(a.second, mp[node][a.first]);
            }
        }
    }
    mp[node][d] = h;
    if(mp[node].find(d + k) != mp[node].end()){
        ans = min(ans, mp[node][d + k] - h);
    }
}

int best_path(int N, int K, int H[][2], int L[]){
    n = N;
    k = K;
    for(int i = 0; i < n; i++){
        g[H[i][0]].push_back({H[i][1], L[i]});
        g[H[i][1]].push_back({H[i][0], L[i]});
    }
    dfs(0, 0, 0, 0);
    if(ans == oo) return -1;
    return ans;
}

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