Submission #378265

#	Time	Username	Problem	Language	Result	Execution time	Memory
378265		Blerargh	Race (IOI11_race)	C++17	9 / 100	301 ms	61940 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;
        }
    }

    cerr << "1Node" _ u _ ": ";
    for (auto st : s[u]) {
        cerr << "{" << st.first << "," _ st.second << "}, ";
    }
    cerr << '\n';
    cerr << maxid _ maxsize _ '\n';

    s[u].emplace(dis, dep);
    if (maxid != -1) s[u].swap(s[maxid]);

    cerr << "2Node" _ u _ ": ";
    for (auto st : s[u]) {
        cerr << "{" << st.first << "," _ st.second << "}, ";
    }
    cerr << '\n';

    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+2*dis, 0));
            if ((*it).first == k - actdist + 2*dis){
                ans = min(ans, treedist + (*it).second - 2*dep);
                cerr << "Found:" _ "{" << ss.first << "," _ ss.second << "}, {" << (*it).first << "," _ (*it).second << "}\n"; 
            }
        }
        for (auto ss : s[node]) s[u].emplace(ss);
    }

    cerr << "3Node" _ u _ ": ";
    for (auto st : s[u]) {
        cerr << "{" << st.first << "," _ st.second << "}, ";
    }
    cerr << '\n';
}

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: 0 / 12
• Subtask 3: 0 / 22
• Subtask 4: 0 / 57