제출 #1366063

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1366063		shrimb	경주 (Race) (IOI11_race)	C++20	100 / 100	244 ms	73212 KiB

race

#include "race.h"
#include <bits/stdc++.h>
using namespace std;
// #define int long long
#define mod 1000000007
const int maxn=200004;
int n,k,ans=-1,dep[maxn],wet[maxn];
map<int,int> ma[maxn];
vector<pair<int,int>> v[maxn];

void check(int i,int wa,int wl,int da,int dl)
{
    int j=k-wa + 2*wl;
    if(ma[i].count(j))
    {
        int g=da+ma[i][j]- 2*dl;
        if(ans==-1||ans>g)
        {
            ans=g;
        }
    }
}

void mer(int i,int w,int d)
{
    if(ma[i].count(w))
    {
        if(ma[i][w]>d)
        {
            ma[i][w]=d;
        }
    }
    else
    {
        ma[i][w]=d;
    }
}

void df(int i,int j)
{
    dep[i]=dep[j]+1;
    int m=-1;
    for(auto [k,w] : v[i])
    {
        if(k!=j)
        {
            wet[k]=wet[i]+w;
            df(k,i);
            if(m==-1||ma[k].size()>=ma[m].size())
            {
                m=k;
            }
        }
    }

    if(m!=-1)
    {
        swap(ma[i],ma[m]);
    }

    check(i,wet[i],wet[i],dep[i],dep[i]);
    mer(i,wet[i],dep[i]);

    for(auto [k,w] : v[i])
    {
        if(k!=j&&k!=m)
        {
            for(auto [we,de] : ma[k])
            {
                check(i,we,wet[i],de,dep[i]);
            }
            for(auto [we,de] : ma[k])
            {
                mer(i,we,de);
            }
        }
    }



}



int best_path(int N,int K,int H[][2],int L[])
{
    k=K;
    for(int i=0;i<N-1;i++)
    {
        int v1,v2,w;
        v1=H[i][0];
        v2=H[i][1];
        w=L[i];
        v[v1].push_back({v2,w});
        v[v2].push_back({v1,w});
    }

    df(0,N+7);


    return ans;
}

• 서브태스크 1: 9 / 9
• 서브태스크 2: 12 / 12
• 서브태스크 3: 22 / 22
• 서브태스크 4: 57 / 57