Submission #400197

#	Time	Username	Problem	Language	Result	Execution time	Memory
400197		MOUF_MAHMALAT	Race (IOI11_race)	C++14	100 / 100	1997 ms	48796 KiB

race

#include "race.h"
#include<bits/stdc++.h>
#define f first
#define s second
using namespace std;
typedef int ll;
vector<vector<pair<ll,ll> > >v;
ll x,y,p[200009],k,ans=1e7;
bool b[200009];
deque<ll>dq;
map<ll,ll>op;
void dfs(ll d,ll pp)
{
    p[d]=1;
    for(auto z:v[d])
    {
        if(z.f==pp||b[z.f])
            continue;
        dfs(z.f,d);
        p[d]+=p[z.f];
    }
}
ll center(ll d,ll pp)
{
    for(auto z:v[d])
    {
        if(z.f==pp||b[z.f])
            continue;
        if(p[z.f]*2>y)
            return center(z.f,d);
    }
    return d;
}
void add(ll d,ll pp,ll sum,ll h)
{
    if(sum>k)
        return;
    if(op[k-sum]||sum==k)
        ans=min(ans,op[k-sum]+h);
    for(auto z:v[d])
    {
        if(z.f==pp||b[z.f])
            continue;
        add(z.f,d,sum+z.s,h+1);
    }
}
void ok(ll d,ll pp,ll sum,ll h)
{
    if(op[sum])
        op[sum]=min(op[sum],h);
    else
        op[sum]=h;
    for(auto z:v[d])
    {
        if(z.f==pp||b[z.f])
            continue;
        ok(z.f,d,sum+z.s,h+1);
    }
}
ll best_path(ll n, ll K, ll H[][2], ll co[])
{
    k=K;
    if(k==0)
        return 0;
    v.resize(n);
    for(ll i=0; i<n-1; i++)
    {
        x=H[i][0], y=H[i][1];
        v[x].push_back({y,co[i]});
        v[y].push_back({x,co[i]});
    }
    dq.push_back(0);
    while(dq.size())
    {
        x=dq.front();
        dq.pop_front();
        dfs(x,-1);
        y=p[x];
        x=center(x,-1);
        op.clear();
        b[x]=1;
        for(auto z:v[x])
        {
            if(b[z.f])
                continue;
            add(z.f,x,z.s,1);
            ok(z.f,x,z.s,1);
            dq.push_back(z.f);
        }
    }
    if(ans>=n)
        ans=-1;
    return ans;
}

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