제출 #1288502

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

race

#include<bits/stdc++.h>
#include "race.h"
using namespace std;
const int maxn=2e5+10;
struct c
{
    int x,t;
};
vector<c> v[maxn];
int n,k;
long long d[maxn];
int r[maxn];
map<long long,int> m[maxn];
int ans=1e9;
void dfs1(int i,int par)
{
    r[i]=r[par]+1;
    for(auto nb:v[i])
    {
        if(nb.x==par)
        {
            continue;
        }
        d[nb.x]=d[i]+nb.t;
        dfs1(nb.x,i);
    }
}
void unite(int x,int y)
{
    if(m[x].size() < m[y].size())
        swap(m[x], m[y]);

    for(auto [key,value] : m[y])
    {
        long long need = k - key + 2*d[x];
        if(m[x].count(need))
            ans = min(ans, m[x][need] + value - 2*r[x]);
    }
    for(auto [key,value] : m[y])
    {
        if(!m[x].count(key))
            m[x][key] = value;
        else
            m[x][key] = min(m[x][key], value);
    }
}
//k=d[u]+d[v]-2*d[lca(x,y)]
void dfs(int i,int par)
{
    for(auto nb:v[i])
    {
        if(nb.x==par)
        {
            continue;
        }
        //cout<<i<<' '<<nb.x<<' '<<"||"<<endl;
        dfs(nb.x,i);
        unite(i,nb.x);
    }
}
int best_path(int N,int K,int h[][2],int l[])
{
    n=N;
    k=K;
    for(int i=0; i<n-1; i++)
    {
        //cout<<h[i][0]<<' '<<h[i][1]<<' '<<l[i]<<endl;
        v[h[i][0]].push_back({h[i][1],l[i]});
        v[h[i][1]].push_back({h[i][0],l[i]});
    }
    r[0]=-1;
    dfs1(0,0);
    for(int i=0; i<n; i++)
    {
        //cout<<d[i]<<' '<<r[i]<<endl;
        m[i][d[i]]=r[i];
    }
    dfs(0,0);
    if(ans==1e9)
    {
        return -1;
    }
    return ans;
}
/*
11 12
0 1 3
0 2 4
2 3 5
3 4 4
4 5 6
0 6 3
6 7 2
6 8 5
8 9 6
8 10 7
*/

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