Submission #926805

#	Time	Username	Problem	Language	Result	Execution time	Memory
926805		Art_ogo	Race (IOI11_race)	C++17	9 / 100	70 ms	48540 KiB

race

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

#define ve vector
#define ll long long
#define fi first
#define se second

using namespace std;

typedef pair<ll, ll> pll;

const int MAXN = 1e6 + 10;
ll k;

ve<pll> g[MAXN];
map<ll, ll>* st[MAXN];
pll add[MAXN];
ll res;

void dfs(int v, int p){
    pll mx = {-1, -1};
    for(auto& to : g[v])
        if(to.fi != p){
            dfs(to.fi, v);
            if(mx.fi == -1 || st[to.fi]->size() > st[mx.fi]->size())
                mx = to;
        }
    if(mx.fi == -1){
        st[v] = new map<ll, ll>();
        return;
    }
    st[v] = st[mx.fi];
    add[v] = add[mx.fi];
    add[v].fi += mx.se;
    add[v].se++;
    (*st[v])[mx.se - add[v].fi] = min((*st[v])[mx.se - add[v].fi], 1 - add[v].se);
    for(auto& to : g[v]){
        if(to.fi != p && to != mx){
            for(auto j : *st[to.fi]){
                pll i = j;
                i.fi += add[to.fi].fi + to.se;
                i.se += add[to.se].se + 1;
                ll cur = (k - i.fi) - add[v].fi;
                if(st[v]->find(cur) != st[v]->end())
                    res = min(res, (*st[v])[cur] + add[v].se + i.se);
            }
            (*st[v])[to.fi - add[v].fi] = min((*st[v])[to.fi - add[v].fi], to.se - add[v].se);
        }
    }

    ll cur = k - add[v].fi;
    if(st[v]->find(cur) != st[v]->end())
        res = min(res, (*st[v])[cur] + add[v].se);    
    st[v]->insert({-add[v].fi, -add[v].se});
    //cout << res << endl;
}

int best_path(int N, int K, int H[][2], int L[])
{
    k = K;
    for(int i = 0; i < N; i++){
        g[i].clear();
        delete(st[i]);
        add[i] = {0, 0};
        res = 1e18;
    }
    for(int i = 0; i < N - 1; 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);
    return res == 1e18 ? -1 : res;
}

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