제출 #926744

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
926744		Art_ogo	경주 (Race) (IOI11_race)	C++17	9 / 100	87 ms	51204 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>();
        st[v]->insert({0, 0});
        return;
    }
    st[v] = st[mx.fi];
    add[v] = add[mx.fi];
    add[v].fi += mx.se;
    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;
                i.se += add[to.se].se;
                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 + 1);
                (*st[v])[i.fi - add[v].fi] = min((*st[v])[i.fi - add[v].fi], i.se - add[v].se);
            }
        }
    for(auto& to : g[v])
        if(to.fi != p)
            (*st[v])[to.se - add[v].fi] = min((*st[v])[to.se - add[v].fi], 1 - 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);    
    //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