제출 #543165

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
543165		__Variatto	경주 (Race) (IOI11_race)	C++17	0 / 100	3065 ms	23764 KiB

race

#include <bits/stdc++.h>
#include "race.h"
using namespace std;
#define pb push_back
#define fi first
#define se second
#define ll long long
const int MAX=2e5+10, MAXV=1e6+10;
vector<pair<int,int>>g[MAXV];
int n, k, centr, podd[MAXV], o[MAXV];
int odw[MAXV], wynik=MAXV, mini[MAXV];
void dfs(int v, int oj, int roz){
    podd[v]=1, o[v]=oj;
    int maxi=0;
    for(auto s:g[v]){
        if(s.fi!=oj && !odw[s.fi]){
            dfs(s.fi, v, roz);
            maxi=max(maxi, podd[s.fi]);
            podd[v]+=podd[s.fi];
        }
    }
    if(maxi<=roz/2 && (roz-podd[v])<=roz/2)
        centr=v;
}
void zlicz(int v, int oj, int st, int akt, int ile){
    if(akt>k) return;
    wynik=min(wynik, mini[k-akt]+ile);
    for(auto s:g[v]){
        if(s.fi!=oj&&odw[s.fi]<=st) continue;
        zlicz(s.fi, v, st, akt+s.se, ile+1);
    }
}
void dodaj(int v, int oj, int st, int akt, int ile){
    if(akt>k) return;
    mini[akt]=min(mini[akt], ile);
    for(auto s:g[v]){
        if(s.fi!=oj&&odw[s.fi]<=st) continue;
        dodaj(s.fi, v, st, akt+s.se, ile+1);
    }
}
void zeruj(int v, int oj, int st, int akt, int ile){
    if(akt>k) return;
    mini[akt]=MAXV;
    for(auto s:g[v]){
        if(s.fi!=oj&&odw[s.fi]<=st) continue;
        zeruj(s.fi, v, st, akt+s.se, ile+1);
    }
}
void rek(int aktc, int roz, int st){
    odw[aktc]=st;
    for(auto s:g[aktc]){
        if(!odw[s.fi]){
            int newR=podd[s.fi];
            if(s.fi==o[aktc]) newR=roz-podd[aktc];
            centr=0;
            dfs(s.fi, s.fi, newR);
            rek(centr, newR, st+1);
        }
    }
    mini[0]=0;
    for(auto s: g[aktc]){
        zlicz(s.fi, s.fi, st, 0, 0);
        dodaj(s.fi, s.fi, st, 0, 0);
    }
    for(auto s: g[aktc])
        zeruj(s.fi, s.fi, st, 0, 0);
}
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]].pb({H[i][1], L[i]}), g[H[i][1]].pb({H[i][0], L[i]});
    for(int i=0; i<=k; i++)
        mini[i]=MAXV;
    dfs(0, 0, n);
    rek(centr, n, 1);
    if(wynik==MAXV) wynik=-1;
    return wynik;
}
/*int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int N, K;
    cin>>N>>K;
    int H[N+10][2], L[N+10];
    for(int i=0; i<N-1; i++)
        cin>>H[i][0]>>H[i][1]>>L[i];
    cout<<best_path(N, K, H, L)<<"\n";

}*/

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