Submission #774558

#	Time	Username	Problem	Language	Result	Execution time	Memory
774558		teokakabadze	Race (IOI11_race)	C++17	100 / 100	431 ms	84604 KiB

race

#include "race.h"
#include<bits/stdc++.h>
#define f first
#define s second
#define pb push_back
#define n 200005
#define pii pair<int, int>
using namespace std;

int ans = 1e9, i, k, s[n], h[n];
vector<pii> v[n];
map<int, int> m[n];

void dfs(int u, int p)
{
    for(auto x : v[u])
    if(x.f != p)
    {
        s[x.f] = s[u] + x.s;
        h[x.f] = h[u] + 1;
        m[x.f][s[x.f]] = h[x.f];
        dfs(x.f, u);
    }
}

void dfs1(int u, int p)
{
    for(auto x : v[u])
    if(x.f != p)
    {
        dfs1(x.f, u);
        if(m[x.f].size() > m[u].size()) swap(m[u], m[x.f]);
        for(auto y : m[x.f])
        if(m[u].find(k + 2 * s[u] - y.f) != m[u].end()) ans = min(ans, m[u][k + 2 * s[u] - y.f] + y.s - 2 * h[u]);
        for(auto y : m[x.f])
        if(m[u].find(y.f) != m[u].end()) m[u][y.f] = min(m[u][y.f], y.s);
        else m[u][y.f] = y.s;
    }
}

int best_path(int N, int K, int H[][2], int L[])
{
    k = K;
    for(i = 0; i < N - 1; i++)
    {
        v[H[i][0]].pb({H[i][1], L[i]});
        v[H[i][1]].pb({H[i][0], L[i]});
    }
    m[0][0] = 0;
    dfs(0, 0);
    dfs1(0, 0);
    if(ans == 1e9) return -1;
    return ans;
}

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