제출 #875777

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
875777		fucfan	Race (IOI11_race)	C++14	100 / 100	1996 ms	159640 KiB

race

// #include "race.h"
#include<bits/stdc++.h>
#define fi first
#define se second
#define ull unsigned long long
#define ll long long
#define BIT(a , b) ((a >> b) & 1)
#define turnOn(a , b) ((a) | (1 << (b)))
#define turnOff(a , b) ((a) ^ (1 << (b)))
#define pii pair<ll , ll>
#define pb push_back
#define nl cout << "\n";
#define __ <<" "<<
#define mem(a, b) memset((a), (b), sizeof((a)))
#define all(c) (c).begin(), (c).end()
#define file "test"
using namespace std;

const int oo = 1e9 + 7;
const int mod = 1e9 + 7;
const int N = 2e5 + 5;
const int LOG = 20;

int n , child[N];
ll depth[N] , ans = oo;
ll k;
ll dist[N];
vector <pii> adj[N]; 
vector <int> vt[N];
map <ll , set<ll>> cnt;

void getsz(int i , int p){
    child[i] = 1;
    for(auto it : adj[i]){
        int j = it.fi;
        if(j == p) continue;
        depth[j] = depth[i] + 1;
        dist[j] = dist[i] + it.se;
        getsz(j , i);
        child[i] += child[j];
    }
}

void sack(int i , int p , bool keep){
    int best_node = -1;
    int Max = -1;
    for(auto it : adj[i]){
        int j = it.fi;
        if(j == p) continue;
        if(child[j] > Max){
            Max = child[j];
            best_node = j;
        }
    }

    for(auto it : adj[i]){
        int j = it.fi;
        if(j != p && j != best_node) sack(j , i , 0);
    }

    if(best_node != -1){
        sack(best_node , i , 1);
        swap(vt[i] , vt[best_node]);
    }

    vt[i].pb(i);

    // cout << i << ' ' << cnt[dist[i] + k].size() << ' ' << dist[i] + k << ' ' << keep << '\n';

    if(cnt[dist[i] + k].size()){
        // cout << "ff\n";
        ans = min(ans , *cnt[dist[i] + k].begin() - depth[i]);
    }
    cnt[dist[i]].insert(depth[i]);

    // cout << i << ' ' << dist[i] << ":\n";

    for(auto it : adj[i]){
        int j = it.fi;
        if(j == p || j == best_node) continue;
        for(auto x : vt[j]){
            ll tmp = k - (dist[x] - dist[i]) + dist[i];
            // cout << dist[x] << ' ' << dist[i] << ' ' << tmp << '\n';
            if(cnt[tmp].size()){
                // cout << i << ' ' << x << ' ' << tmp << '\n';
                ans = min(ans , depth[x] + *cnt[tmp].begin() - 2 * depth[i]);
            }
        }
        
        for(auto x : vt[j]){
            cnt[dist[x]].insert(depth[x]);
            vt[i].pb(x);
        }
    }
    // cout << i << ' ' << keep << ":\n";

    // for(auto j : vt[i]) cout << j << ' ';
    // nl;
    
    if(!keep){
        for(auto x : vt[i]){
            cnt[dist[x]].erase(depth[x]);
            // cout << x << '/' << cnt[dist[x]].size() << ' ';
        }
        // nl;
    }
}

int best_path(int _N, int _K, int _H[][2], int _L[])
{
    // if(_K == 1) return 0;
    n = _N;
    k = _K;
    for(int i = 0 ; i < n - 1 ; i++){
        int u , v , w;
        u = _H[i][0];
        v = _H[i][1];
        w = _L[i];
        u++;
        v++;
        adj[u].pb({v , w});
        adj[v].pb({u , w});
    }
    getsz(1 , 0);
    sack(1 , 0 , 0);
    if(ans != oo) return ans;
    else return -1;
}

// void run_with_file(){
//     if(fopen(file".inp","r")){
//         freopen(file".inp","r", stdin);
//         freopen(file".out", "w", stdout);
//     }
// }

// int main(){
//     run_with_file();
//     cin >> n >> k;
//     for(int i = 0 ; i < n - 1 ; i++){
//         int u , v , w;
//         cin >> u >> v >> w;
//         u++;
//         v++;
//         adj[u].pb({v , w});
//         adj[v].pb({u , w});
//     }
//     getsz(1 , 0);
//     sack(1 , 0 , 0);
//     if(ans != oo) cout << ans;
//     else cout << -1;
// }

/*      UwU      */ 

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