Submission #875325

#	Time	Username	Problem	Language	Result	Execution time	Memory
875325		fucfan	Race (IOI11_race)	C++14	43 / 100	1213 ms	127024 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<int, int>
#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 , k , child[N] , depth[N] , ans = oo;
ll dist[N];
vector <pii> adj[N]; 
vector <int> vt[N];
map <ll , set<int>> 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()){
                ans = min(ans , depth[x] + *cnt[tmp].begin() - 2 * depth[i]);
            }
            cnt[dist[x]].insert(depth[x]);
            vt[i].pb(x);
        }
    }
    // cout << i << ": ";

    // for(auto j : vt[i]) cout << j << ' ';
    // nl;
    
    if(!keep){
        for(auto x : vt[i]){
            cnt[dist[x]].erase(depth[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++){
        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;
}

/*      UwU      */

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