제출 #651827

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
651827		andrei_boaca	경주 (Race) (IOI11_race)	C++14	100 / 100	1353 ms	54120 KiB

race

#include <bits/stdc++.h>
#include "race.h"
//#include "grader.cpp"
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
ll n,k,ans=1e9,dist[200005],niv[200005],nr[200005],par[200005];
vector<int> vals;
vector<vector<pii>> allvals;
int mini[1000005],m1[1000005],m2[1000005];
struct date
{
    ll a,b,cost;
} G[200005];
bool edgeuse[200005];
vector<int> muchii[200005];
void build(int nod)
{
    nr[nod]=1;
    for(int i:muchii[nod])
    {
        int a=G[i].a,b=G[i].b;
        int x=(a^b^nod);
        if(!edgeuse[i]&&x!=par[nod])
        {
            par[x]=nod;
            build(x);
            nr[nod]+=nr[x];
        }
    }
}
void reroot(int nod,int fiu)
{
    nr[nod]-=nr[fiu];
    nr[fiu]+=nr[nod];
    par[fiu]=0;
    par[nod]=fiu;
}
int findcentroid(int nod)
{
    par[nod]=0;
    build(nod);
    bool found=0;
    while(!found)
    {
        found=1;
        for(int i:muchii[nod])
            if(!edgeuse[i])
            {
                int a=G[i].a,b=G[i].b;
                int x=(a^b^nod);
                if(nr[x]>nr[nod]/2)
                {
                    reroot(nod,x);
                    nod=x;
                    found=0;
                    break;
                }
            }
    }
    return nod;
}
void dfs(int nod)
{
    if(dist[nod]==k)
        ans=min(ans,niv[nod]);
    for(int i:muchii[nod])
        if(!edgeuse[i])
        {
            int a=G[i].a,b=G[i].b;
            int x=(a^b^nod);
            if(x!=par[nod])
            {
                par[x]=nod;
                niv[x]=niv[nod]+1;
                dist[x]=dist[nod]+G[i].cost;
                dfs(x);
            }
        }
}
void dfs1(int nod)
{
    if(dist[nod]<k&&dist[nod]>0)
    {
        vals.push_back(dist[nod]);
        mini[dist[nod]]=min(1LL*mini[dist[nod]],niv[nod]);
    }
    for(int i:muchii[nod])
        if(!edgeuse[i])
        {
            int a=G[i].a,b=G[i].b;
            int x=(a^b^nod);
            if(par[nod]!=x)
                dfs1(x);
        }
}
void go(int nod)
{
    int root=findcentroid(nod);
    dist[root]=0;
    niv[root]=0;
    par[root]=0;
    dfs(root);
    allvals.clear();
    for(int i:muchii[root])
        if(!edgeuse[i])
        {
            vals.clear();
            int a=G[i].a,b=G[i].b;
            int x=(a^b^root);
            dfs1(x);
            sort(vals.begin(),vals.end());
            vals.erase(unique(vals.begin(),vals.end()),vals.end());
            vector<pii> mine;
            for(int j:vals)
            {
                if(mini[j]<m1[j])
                {
                    m2[j]=m1[j];
                    m1[j]=mini[j];
                }
                else if(mini[j]<m2[j])
                    m2[j]=mini[j];
                mine.push_back({j,mini[j]});
                mini[j]=1e9;
            }
            allvals.push_back(mine);
        }
    for(auto v:allvals)
    {
        for(pii a:v)
            mini[a.first]=a.second;
        for(pii a:v)
        {
            int need=k-a.first;
            if(need==0||need==k)
                continue;
            ll val=a.second;
            if(m1[need]==mini[need])
                val+=m2[need];
            else
                val+=m1[need];
            ans=min(ans,val);
        }
        for(pii a:v)
            mini[a.first]=1e9;
    }
    for(auto v:allvals)
    {
        for(pii a:v)
            m1[a.first]=m2[a.first]=1e9;
    }
    for(int i:muchii[root])
        if(!edgeuse[i])
        {
            edgeuse[i]=1;
            int a=G[i].a,b=G[i].b;
            int x=(a^b^root);
            go(x);
        }
}
int best_path(int N, int K, int H[][2], int L[])
{
    n=N;
    k=K;
    for(int i=1;i<=k;i++)
    {
        m1[i]=m2[i]=1e9;
        mini[i]=1e9;
    }
    for(int i=0;i<n-1;i++)
    {
        int a=H[i][0];
        int b=H[i][1];
        a++;
        b++;
        G[i+1]={a,b,0};
        muchii[a].push_back(i+1);
        muchii[b].push_back(i+1);
    }
    for(int i=0;i<n-1;i++)
        G[i+1].cost=L[i];
    go(1);
    if(ans<=n)
        return ans;
    return -1;
}

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