제출 #1272496

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

race

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <iomanip>
#include <numeric>
#include <vector>
#include <queue>
#include <stack>
#include <string>
#include <set>
#include <unordered_map>
#include "race.h"

#define hyathu main
#define popcorn __builtin_popcount

using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;

constexpr int mmb = 2e5 + 69;
const ld pi = atan(1) * 4;

int f[mmb], v[mmb * 2];
ll w[mmb * 2];
int p[mmb];
unordered_map <ll, int> dist;
ll d[mmb], K;
int h[mmb];
int ans = 2e9;

int el[mmb], in[mmb], ot[mmb], cnt;

void prepare(int i){
    in[i] = ++cnt;
    el[cnt] = i;
    for(int id = f[i]; id < f[i + 1]; ++id){
        int nx = v[id];
        ll ad = w[id];
        if(nx == p[i]) continue;
        
        p[nx] = i;
        d[nx] = d[i] + ad;
        h[nx] = h[i] + 1;
        prepare(nx);
    }
    ot[i] = cnt;
}

void dfs(int i){
    int bigboi = -1, bigcnt = 0;
    
    for(int id = f[i]; id < f[i + 1]; ++id){
        int nx = v[id];
        ll ad = w[id];
        if(nx == p[i]) continue;
        
        if(ot[nx] - in[nx] + 1 > bigcnt){
            bigcnt = ot[nx] - in[nx] + 1;
            bigboi = nx;
        }
    }
    
    for(int id = f[i]; id < f[i + 1]; ++id){
        int nx = v[id];
        if(nx == p[i] || nx == bigboi) continue;
        
        dfs(nx);
        dist.clear();
    }
    
    if(bigboi != -1)
        dfs(bigboi);
    
    for(int id = f[i]; id < f[i + 1]; ++id){
        int nx = v[id];
        if(nx == p[i] || nx == bigboi) continue;
        
        for(int j = in[nx]; j <= ot[nx]; ++j){
            int nd = el[j];
            auto it = dist.find(K + 2 * d[i] - d[nd]);
            if(it != dist.end())
                ans = min(ans, h[nd] + it->second - 2 * h[i]);
        }
        for(int j = in[nx]; j <= ot[nx]; ++j){
            int nd = el[j];
            auto res = dist.emplace(d[nd], h[nd]);
            if(!res.second)
                res.first->second = min(res.first->second, h[nd]);
        }
    }
        
    auto it = dist.find(K + d[i]);
    if(it != dist.end())
        ans = min(ans, it->second - h[i]);
    auto res = dist.emplace(d[i], h[i]);
    if(!res.second)
        res.first->second = min(res.first->second, h[i]);
}

int best_path(int n, int k, int h[][2], int l[]){
    fill(p, p + n, -1);
    
    K = k;
    for(int i = 0; i < n - 1; ++i){
        ++f[h[i][0]];
        ++f[h[i][1]];
    }
    for(int i = 1; i <= n; ++i)
        f[i] += f[i - 1];
    for(int i = 0; i < n - 1; ++i){
        v[--f[h[i][0]]] = h[i][1];
        w[f[h[i][0]]] = l[i];
        v[--f[h[i][1]]] = h[i][0];
        w[f[h[i][1]]] = l[i];
    }
    
    prepare(0);
    
    dfs(0);
    return (ans == 2e9 ? -1 : ans);
}

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