Submission #399929

#	Time	Username	Problem	Language	Result	Execution time	Memory
399929		MOUF_MAHMALAT	Race (IOI11_race)	C++14	0 / 100	1 ms	332 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,ans=1e9,p[200009],k;
bool b[200009];
deque<ll>dq;
map<ll,ll>op,mp;
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(mp[sum])
        mp[sum]=min(mp[sum],h);
    else
        mp[sum]=h;
    for(auto z:v[d])
    {
        if(z.f==pp||b[z.f])
            continue;
        add(z.f,d,sum+z.s,h+1);
    }
}
int best_path(ll n, ll K, ll H[][2], ll co[])
{
    k=K;
    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;
            mp.clear();
            add(z.f,x,z.s,1);
            for(auto u:mp)
            {
                if(u.s==0)
                    continue;
                if(u.f==k)
                    ans = min(ans, u.s);
                if(op[k-u.f])
                    ans = min(ans, u.s+op[k-u.f]);
                if(op[u.f])
                    op[u.f] = min(op[u.f],u.s);
                else
                    op[u.f] = u.s;
            }
            dq.push_back(z.f);
        }
    }
    if(ans==1e9)
        ans=-1;
    return ans;
}

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