Submission #674295

#	Time	Username	Problem	Language	Result	Execution time	Memory
674295		lam	Race (IOI11_race)	C++14	43 / 100	712 ms	262144 KiB

race

#include <bits/stdc++.h>
using namespace std;
typedef pair<long long,long long> ii;
#define ff first
#define ss second
const long long maxn = 1e6 + 10;
map<long long,long long> mp[maxn];
long long n;
long long k;
vector <ii> adj[maxn];
long long s[maxn],dau[maxn];
long long ans = 1e9;

long long get_sz(long long x, long long p)
{
    s[x]=1;
    for (ii i:adj[x])
        if (i.ff!=p&&!dau[i.ff]) s[x]+=get_sz(i.ff,x);
    return s[x];
}

long long find_centroid(long long x, long long p, long long sz)
{
    for (ii i:adj[x])
        if (i.ff!=p&&!dau[i.ff]&&s[i.ff]*2>sz) return find_centroid(i.ff,x,sz);
    return x;
}

void dfs(long long root, long long x, long long p, long long val, long long depth)
{
    if (val<=k&&mp[root][k-val]) ans=min(ans,depth+mp[root][k-val]);
    if (val==k) ans=min(ans,depth);
    for (ii i:adj[x])
        if (i.ff!=p&&!dau[i.ff]) dfs(root,i.ff,x,1LL*val+i.ss,depth+1);
}
void dfs2(long long root, long long x, long long p, long long val, long long depth)
{
    if (val<=k)
    {
        if (!mp[root][val]) mp[root][val] = depth;
        else mp[root][val]=min(mp[root][val],depth);
    }
    for (ii i:adj[x])
        if (i.ff!=p&&!dau[i.ff]) dfs2(root,i.ff,x,1LL*val+i.ss,depth+1);
}

void decompose(long long x)
{
    x=find_centroid(x,x,get_sz(x,x));
    dau[x]=1;
    for (ii i:adj[x])
        if (!dau[i.ff])
    {
        dfs(x,i.ff,x,1LL*i.ss,1);
        dfs2(x,i.ff,x,1LL*i.ss,1);
    }
    for (ii i:adj[x])
        if (!dau[i.ff]) decompose(i.ff);
}

ii e[maxn];

int best_path(int N, int K, int H[][2], int L[])
{
    n=N; k=K;
    for (long long i=1; i<=n; i++) adj[i].clear();
    for (long long i=0; i<n-1; i++)
    {
        e[i].ff=H[i][0];
        e[i].ss=H[i][1];
    }
    for (long long i=0; i<n-1; i++)
    {
        long long w=L[i];
        long long u=e[i].ff; long long v=e[i].ss;
        u++; v++;
        adj[u].push_back({v,w});
        adj[v].push_back({u,w});
    }
    decompose(1);
    if (ans==1e9) ans=-1;
    return ans;
}

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