제출 #1266212

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1266212		WH8	Race (IOI11_race)	C++20	100 / 100	292 ms	99472 KiB

race

#include "race.h"
#include <bits/stdc++.h>
using namespace std;
#define iloop(x, n) for (long long i = x; i < n; ++i)
#define jloop(x, n) for (long long j = x; j < n; ++j)
#define kloop(x, n) for (long long k = x; k < n; ++k)
#define dloop(x, n) for (long long d = x; d >= n; --d)
#define int long long
#define pll pair<long long, long long>
#define pii pair<int, int>
#define iii tuple<int, int, int>
#define vi vector<int>
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define endl '\n'
#define g0(a) get<0>(a)
#define g1(a) get<1>(a)
#define g2(a) get<2>(a)
#define g3(a) get<3>(a)
#define dg(x) cerr << #x << ": " << x << endl
#define all(x) x.begin(), x.end()
#define FASTIO               \
    ios::sync_with_stdio(false); \
	cin.tie(0);              \
    cout.tie(0);

int n, k;
vector<vector<pll>> al(200005);
int ans = 1e15;

int os[200005];
vector<multiset<pll>> mem(200005);

int depth[200005];
int pd[200005];

void dfs(int x, int p){
	multiset<pll> bs, ss;
	int bso = 0, sso = 0;
	bs.insert({0, depth[x]});
	for (pll ed : al[x]){
		int it = ed.f;
		if (it == p) continue;
		dfs(it, x);
	}
	//cout << "WE ARE AT " << x << endl;
	for (pll ed: al[x]){
		int it = ed.f;
		if (it == p) continue;
		ss.swap(mem[it]);
		sso = os[it];
		if (ss.size() > bs.size()) {
			bs.swap(ss);
			swap(bso, sso);
		}
		//dg(x);
		//dg(it);
		/*cout << "SS : " ;
		for (auto it : ss){
			cout << "{ " << it.f << ", " << it.s << " }  ";
		}
		cout << endl;
		cout << "BS : " ;
		for (auto it : bs ){
			cout << "{ " << it.f << ", " << it.s << " }  ";
		}
		cout << endl;*/
		for (auto cand : ss){
			// length, endpoint
			int tar = (k - (sso + cand.f)) - bso;
			auto itr = bs.lower_bound({tar, -1e15});
			if (itr != bs.end() and (*itr).f == tar){
				int neu = (*itr).s + cand.s - 2 * depth[x];
				if (neu > 0) ans = min(ans, neu);
			}
		}
		for (auto cand : ss){
			// add to big set, negating offset
			bs.insert({cand.f + sso - bso, cand.s});
		}
	}
	/*cout << "BS AFTER: " ;
	for (auto it : bs){
		cout << "{ " << it.f << ", " << it.s << " }  ";
	}
	cout << endl;*/
	os[x] = bso + pd[x];
	mem[x].swap(bs);
}

void ddfs(int x, int p){
	for (auto it : al[x]){
		if (it.f == p) continue;
		depth[it.f] = depth[x] + 1;
		pd[it.f] = it.s;
		ddfs(it.f, x);
	}
}

int32_t best_path(int32_t N, int32_t K, int32_t H[][2], int32_t L[])
{
	n = N, k = K;
	iloop(0, n-1){
		int a = H[i][0], b = H[i][1];
		int c = L[i];
		al[a].pb({b, c});
		al[b].pb({a, c});
	}
	ddfs(0, -1);
	dfs(0, -1);
	/*cout << "DEPTH\n";
	iloop(0, n) cout << depth[i] << " ";
	cout << "PD\n";
	iloop(0, n) cout << pd[i] << " ";*/

	return (ans == 1e15 ? -1 : ans);
}

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