제출 #1151089

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1151089		danglayloi1	경주 (Race) (IOI11_race)	C++20	100 / 100	393 ms	32092 KiB

race

#include "race.h"
#include <bits/stdc++.h>
#define ii pair<int, int>
#define fi first
#define se second
#define inf 0x3f3f3f3f
using namespace std;
using ll = long long;
const ll mod=1e9+7;
const int nx=2e5+5;
vector<ii> adj[nx];
bool del[nx];
int sz[nx], cnt[1000005], ans=inf, lim;
ll dep[nx];
int go(int p, int u)
{
    sz[u]=1;
    for(auto it:adj[u])
    {
        int v=it.fi;
        if(v!=p && !del[v])
            sz[u]+=go(u, v);
    }
    return sz[u];
}
int centroid(int p, int u, int tre)
{
    for(auto it:adj[u])
    {
        int v=it.fi;
        if(v!=p && !del[v] && sz[v]>tre/2)
            return centroid(u, v, tre);
    }
    return u;
}
void dfs(int p, int u, int hi, bool ok)
{
    if(ok==0)
    {
        if(dep[u]<=lim)
            ans=min(ans, hi+cnt[lim-dep[u]]);
    }
    else if(dep[u]<=lim) cnt[dep[u]]=min(cnt[dep[u]], hi);
    for(auto it:adj[u])
    {
        int v=it.fi;
        if(v!=p && !del[v])
            dep[v]=dep[u]+it.se, dfs(u, v, hi+1, ok);
    }
}
void dfs1(int p, int u)
{
    if(dep[u]<=lim) cnt[dep[u]]=inf;
    for(auto it:adj[u])
        if(it.fi!=p && !del[it.fi])
            dfs1(u, it.fi);
}
void build(int u)
{
    int root=centroid(0, u, go(0, u));
    dep[root]=0;
    for(auto it:adj[root])
    {
        int v=it.fi;
        if(!del[v])
            dep[v]=it.se, dfs(root, v, 1, 0), dfs(root, v, 1, 1);
    }
    ans=min(ans, cnt[lim]);
    dfs1(0, root);
    del[root]=1;
    for(auto it:adj[root])
        if(!del[it.fi])
            build(it.fi);
}
int best_path(int n, int k, int h[][2], int l[])
{
    lim=k;
    for(int i = 0; i < n; i++)
        adj[i].clear();
    for(int i = 0; i < n-1; i++)
        adj[h[i][0]].emplace_back(h[i][1], l[i]), adj[h[i][1]].emplace_back(h[i][0], l[i]);
    for(int i = 0; i <= k; i++)
        cnt[i]=inf;
    build(0);
    if(ans==inf) ans=-1;
    return ans;
}
// int a[nx][2], b[nx];
// int main()
// {
//     a[0][0]=0, a[0][1]=1;
//     a[1][0]=1, a[1][1]=2;
//     a[2][0]=1, a[2][1]=3;
//     int b[nx];
//     b[0]=1, b[1]=2, b[2]=4;
//     cout<<best_path(4, 3, a, b);
// }

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