Submission #1151067

#	Time	Username	Problem	Language	Result	Execution time	Memory
1151067		danglayloi1	Race (IOI11_race)	C++20	0 / 100	230 ms	327680 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=1e6+5;
vector<ii> adj[nx];
bool del[nx];
int sz[nx], cnt[nx], 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[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);
    }
    dfs1(0, root);
    del[root]=1;
    for(auto it:adj[root])
        build(it.fi);
}
int best_path(int n, int k, int h[][2], int l[])
{
    lim=k;
    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(1);
    if(ans==inf) ans=-1;
    return ans;
}

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