제출 #1288496

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

race

#include<bits/stdc++.h>
#include "race.h"
#define endl '\n'
using namespace std;
const long long maxn=2e5+10;
struct c
{
    long long x,t;
};
vector<c> v[maxn];
long long n,k;
long long d[maxn],r[maxn];
map<long long,long long> m[maxn];
int ans=1e9;
void dfs1(long long i,long long 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(long long x,long long y)
{
    cout<<x<<' '<<y<<endl;
    if(m[x].size()<m[y].size())
    {
        swap(m[x],m[y]);
    }
    for(auto [key,value]:m[y])
    {
        if(m[x][key]==0)
        {
            m[x][key]=value;
        }
        else
        {
            m[x][key]=min(m[x][key],value);
        }
        //cout<<key<<' '<<value<<' '<<m[x][key]<<' '<<d[x]<<endl;
        if(m[x].count(k - key + 2*d[x]))
        {
            ans = min(ans*1LL, m[x][k - key + 2*d[x]] + value - 2*r[x]);
        }
    }
}
//k=d[u]+d[v]-2*d[lca(x,y)]
void dfs(long long i,long long 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(long long 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(long long i=0; i<n; i++)
    {
        //cout<<d[i]<<' '<<r[i]<<endl;
        m[i][d[i]]=r[i];
    }
    dfs(0,-1);
    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: 0 / 9
• Subtask 2: 0 / 12
• Subtask 3: 0 / 22
• Subtask 4: 0 / 57