제출 #1233706

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

race

#include <bits/stdc++.h>
#include "race.h"
using namespace std;
const int MAXN=2e5+5,MAXK=1e6+5;
#define ll long long
#define pb push_back
vector<pair<int,int>> adj[MAXN];
int sz[MAXN],k;
bool removed[MAXN];
void subtree_size(int node,int par){
    sz[node]=1;
    for(auto i:adj[node]){
        if(i.first==par || removed[i.first])continue;
        subtree_size(i.first,node);
        sz[node]+=sz[i.first];
    }
}
int centroid(int node,int par,int tot){
    for(auto i:adj[node]){
        if(i.first==par || removed[i.first])continue;
        if(sz[i.first]*2>tot)return centroid(i.first,node,tot);
    }
    return node;
}
pair<int,int> best[MAXK][2];
vector<ll> uniq;
void dfs2(int node,int par,int og,int sum=0,int length=0){
    if(sum<=k) {
        uniq.pb(sum);
        if (best[sum][0].second == og) {
            best[sum][0] = min(best[sum][0], {length, og});
        } else if (best[sum][1].second == og) {
            best[sum][1] = min(best[sum][1], {length, og});
            if(best[sum][1].first<best[sum][0].first)swap(best[sum][0],best[sum][1]);
        } else {
            if (best[sum][0].first > length) {
                best[sum][1]=best[sum][0];
                best[sum][0] = {length, og};
            }
            else best[sum][1] = min(best[sum][1], {length, og});
        }
    }
    bool flag=(og==-1);
    for(auto i:adj[node]){
        if(i.first==par || removed[i.first])continue;
        dfs2(i.first,node,(flag?i.first:og),sum+i.second,length+1);
    }
}
int ans=2e9;
void dfs(int node){
    subtree_size(node,-1);
    int c=centroid(node,-1,sz[node]);
    uniq.clear();
    best[0][0]={0,-1};
    dfs2(c,-1,-1);
    for(auto i:uniq){
        int x=i,req=k-i;
        if(req<0)continue;
        if(best[x][0].second!=best[req][0].second)ans=min(ans,best[x][0].first+best[req][0].first);
        else ans=min({ans,best[x][0].first+best[req][1].first,best[x][1].first+best[req][0].first});
    }
    for(auto i:uniq){
        best[i][0]={2e8,2e8};
        best[i][1]={2e8,2e8};
    }
    removed[c]=1;
    for(auto i:adj[c]){
        if(!removed[i.first])dfs(i.first);
    }
}
int best_path(int N, int K, int H[][2], int L[])
{
    k=K;
    for(int i=0;i<N-1;i++){
        adj[H[i][0]].pb({H[i][1],L[i]});
        adj[H[i][1]].pb({H[i][0],L[i]});
    }
    for(int i=0;i<MAXK;i++){
        best[i][0]={2e8,2e8};
        best[i][1]={2e8,2e8};
    }
    subtree_size(0,-1);
    dfs(0);
    if(ans>N)return -1;
    return ans;
}

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