Submission #378281

#	Time	Username	Problem	Language	Result	Execution time	Memory
378281		Blerargh	Race (IOI11_race)	C++17	100 / 100	490 ms	110696 KiB

race

#include "race.h"
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
#define _ <<" "<<
#define cerr if(false)cerr
 
/*
Test case :
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
2
 
Test case :
4 3
0 1 1
1 2 2
1 3 4
2
 
*/
 
typedef pair<ll,ll> ii;
typedef tuple<ll,ll,ll,ll> tl; //actual dist, tree dist, offset, node
const ll MAXN = 2e5+5;
const ll INF = 1e18;
 
vector<ii> adjlist[MAXN];
bool visited[MAXN];
multiset<ii> s[MAXN];
ll ans=INF, stsize[MAXN], k;
 
void setmerging(ll u, ll dis, ll dep){
    visited[u] = 1;
    stsize[u] = 1;
    ll maxsize=0, maxid=-1;
    for (auto v : adjlist[u]){
        if (visited[v.first]) continue;
        setmerging(v.first, dis+v.second, dep+1);
 
        stsize[u] += stsize[v.first];
        if (stsize[v.first] > maxsize){
            maxsize = stsize[v.first];
            maxid = v.first;
        }
    }
 
    s[u].emplace(dis, dep);
    if (maxid != -1) s[u].swap(s[maxid]);
 
    for (auto v : adjlist[u]){
        ll node = v.first;
        for (auto ss : s[node]){
            ll actdist = ss.first;
            ll treedist = ss.second;
 
            auto it = s[u].lower_bound(make_pair(k-actdist+2ll*dis, 0ll));
            if (it != s[u].end() && (*it).first == k - actdist + 2ll*dis){
                ans = min(ans, treedist + (*it).second - 2ll*dep);
                cerr << "Found:" _ "{" << ss.first << "," _ ss.second << "}, {" << (*it).first << "," _ (*it).second << "}\n"; 
            }
        }
        for (auto ss : s[node]) s[u].emplace(ss);
    }
}
 
int best_path(int N, int K, int H[][2], int L[]){
    k = K;
    for (int i=0; i<N-1; i++){
        ll a = H[i][0], b = H[i][1], w = L[i];
        adjlist[a].emplace_back(b, w);
        adjlist[b].emplace_back(a, w);
    }
    setmerging(0, 0, 0);
    if (ans == INF) return -1;
    else return ans;
}

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