제출 #727869

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
727869		onepunchac168	경주 (Race) (IOI11_race)	C++14	9 / 100	204 ms	50908 KiB

race

// created by Dinh Manh Hung
// onepunchac168
// THPT CHUYEN HA TINH
// HA TINH, VIET NAM
#include <bits/stdc++.h>
#include "race.h"

using namespace std;

//#pragma GCC optimize("O3,unroll-loops,no-stack-protector")
//#pragma GCC target("sse4,avx2,fma")
#define task ""
#define ldb long double
#define pb push_back
#define fi first
#define se second
#define pc pop_back()
#define all(x) begin(x),end(x)
#define uniquev(v) v.resize(unique(all(v))-v.begin())
#define FOR(i,a,b) for (int i=a;i<=b;i++)
#define cntbit(v) __builtin_popcountll(v)
#define gcd(a,b) __gcd(a,b)
#define lcm(a,b) ((1LL*a*b)/__gcd(a,b))
#define mask(x) (1LL<<(x))
#define readbit(x,i) ((x>>i)&1)
#define ins insert

typedef long long ll;
typedef pair <ll,ll> ii;
typedef pair <ll,ii> iii;
typedef pair <ii,ii> iiii;

ll dx[]= {1,-1,0,0,1,-1,1,-1};
ll dy[]= {0,0,-1,1,1,-1,-1,1};

const ldb PI = acos (-1);
//const ll mod=978846151;
//const ll base=29;
const int maxn=1e6+5;
const int mod=1e9+7;
const char nl = '\n';
ll n,k;
vector <ii> vt[200005];
ll res=1e9+5;
map <ll,ll> *mp[200005];
ll sz[200005];
ll sum[200005];
ll path[200005];
void dfsa(int u,int vv)
{
    sz[u]=1;
    for (auto v:vt[u])
    {
        if (v.fi==vv)
        {
            continue;
        }
        sum[v.fi]=sum[u]+v.se;
        path[v.fi]=path[u]+1;
        dfsa(v.fi,u);
        sz[u]+=sz[v.fi];
    }
}
void dfs(int u,int vv)
{
    int bigchild=-1;
    for (auto v:vt[u])
    {
        if (v.fi==vv)
        {
            continue;
        }
        if (bigchild==-1||sz[v.fi]>sz[bigchild])
        {
            bigchild=v.fi;
        }
    }
    if (bigchild!=-1)
    {
        dfs(bigchild,u);
        mp[u]=mp[bigchild];
    }
    else
    {
        mp[u]=new map <ll,ll>;
    }
    ll ss=sum[u]+k;
    ll a1=(*mp[u])[ss];
    if (a1!=0)
    {
        res=min(res,a1-path[u]);
    }
    ll aa=(*mp[u])[sum[u]];
    if (sum[u]==k)
    {
        res=min(res,path[u]);
    }
    if (aa==0||path[u]<aa)
    {
        (*mp[u])[sum[u]]=path[u];
    }
    for (auto v:vt[u])
    {
        if (v.fi==vv||v.fi==bigchild)
        {
            continue;
        }
        dfs(v.fi,u);
        for (auto cnt:*mp[v.fi])
        {
            ll aa=k+2*sum[u]-cnt.fi;
            ll pp=(*mp[u])[aa];
            if (pp!=0)
            {
                res=min(res,pp+cnt.se-2*path[u]);
            }
        }
        for (auto cnt:*mp[v.fi])
        {
            ll aa=(*mp[u])[cnt.fi];
            if (aa==0||cnt.se<aa)
            {
                (*mp[u])[cnt.fi]=cnt.se;
            }
        }
    }
}
int best_path(int N, int K, int H[][2], int L[])
{
    n=N;
    k=K;
    for (int i=0;i<n-1;i++)
    {
        ll aa=H[i][0];
        ll bb=H[i][1];
        ll w=L[i];
        vt[aa].pb({bb,w});
        vt[bb].pb({aa,w});
    }
    sum[0]=0;
    path[0]=1;
    dfsa(0,-1);
    dfs(0,-1);
    if (res==1e9+5)
    {
        return -1;
    }
    return res;
}

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