Submission #543162

#	Time	Username	Problem	Language	Result	Execution time	Memory
543162		__Variatto	Race (IOI11_race)	C++17	0 / 100	3068 ms	4948 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[MAX];
int n, k, centr, podd[MAX], o[MAX];
int odw[MAX], wynik=MAXV, mini[MAX];
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;
    //cout<<v<<" "<<st<<" "<<mini[k-akt]<<" "<<ile<<"\n";
    wynik=min(wynik, mini[k-akt]+ile);
    for(auto s:g[v]){
        if(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(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(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;
}

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