Submission #1281718

#	Time	Username	Problem	Language	Result	Execution time	Memory
1281718		blackscreen1	Race (IOI11_race)	C++20	100 / 100	403 ms	104248 KiB

race

#include "race.h"
#include <bits//stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef tree<long long, null_type, less<long long>, rb_tree_tag,
             tree_order_statistics_node_update>
    ordered_set;
typedef tree<long long, null_type, less_equal<long long>, rb_tree_tag,
             tree_order_statistics_node_update>
    ordered_multiset;
#define ll long long
#define ld long double
#define iloop(m, h) for (ll i = m; i != h; i += (m < h ? 1 : -1))
#define jloop(m, h) for (auto j = m; j != h; j += (m < h ? 1 : -1))
#define kloop(m, h) for (auto k = m; k != h; k += (m < h ? 1 : -1))
#define lloop(m, h) for (auto l = m; l != h; l += (m < h ? 1 : -1))
#define iloop_(m, h, g) for (auto i = m; i != h; i += g)
#define jloop_(m, h, g) for (auto j = m; j != h; j += g)
#define kloop_(m, h, g) for (auto k = m; k != h; k += g)
#define lloop_(m, h, g) for (auto l = m; l != h; l += g)
#define getchar_unlocked _getchar_nolock // comment before submission
#define pll pair<ll, ll>
#define plll pair<ll, pll>
#define pllll pair<pll, pll>
#define vll vector<ll>
#define qll queue<ll>
#define dll deque<ll>
#define pqll priority_queue<ll>
#define gll greater<ll>
#define INF 1000000000000000
#define MOD1 1000000007
#define MOD2 998244353
#define MOD3 1000000009
mt19937 rng(chrono::system_clock::now().time_since_epoch().count());
ll n, k, an = INF;
vector<pll> adj[200005];
map<ll, ll> stm[200005];
ll cups[200005], cups2[200005];
ll dfs(ll nd, ll pr) {
	stm[nd][0] = 0;
	vector<pll> mg;
	ll crt = nd;
	for (auto it : adj[nd]) {
		if (it.second != pr) {
			mg.push_back({it.first, dfs(it.second, nd)});
		}
	}
	for (auto it : mg) {
		bool swp = 0;
		if (stm[crt].size() > stm[it.second].size()) {swap(crt, it.second); swp = 1;}
		for (auto it2 : stm[crt]) {
			if (stm[it.second].find(k - it.first - (it2.first + cups[crt]) - cups[it.second]) != stm[it.second].end()) {
				an = min(an, stm[it.second][k - it.first - (it2.first + cups[crt]) - cups[it.second]] + cups2[it.second] + it2.second + cups2[crt] + 1);
			}
		}
		swap(crt, it.second);
		if (!swp) {cups2[crt]++, cups[crt] += it.first;}
		for (auto it2 : stm[it.second]) {
			if (swp) {
				if (stm[crt].find(it2.first + cups[it.second] - cups[crt] + it.first) != stm[crt].end()) {
					stm[crt][it2.first + cups[it.second] - cups[crt] + it.first] = min(stm[crt][it2.first + cups[it.second] - cups[crt] + it.first], it2.second + cups2[it.second] + 1 - cups2[crt]);
				}
				else stm[crt][it2.first + cups[it.second] - cups[crt] + it.first] = it2.second + cups2[it.second] + 1 - cups2[crt];
			}
			else {
				if (stm[crt].find(it2.first + cups[it.second] - cups[crt]) != stm[crt].end()) {
					stm[crt][it2.first + cups[it.second] - cups[crt]] = min(stm[crt][it2.first + cups[it.second] - cups[crt]], it2.second + cups2[it.second] - cups2[crt]);
				}
				else stm[crt][it2.first + cups[it.second] - cups[crt]] = it2.second + cups2[it.second] - cups2[crt];
			}
		}
	}
	//cout << nd << "," << crt << ":" << cups[crt] << "," << cups2[crt] << "\n";
	//for (auto it : stm[crt]) cout << it.first << " " << it.second << "\n";
	return crt;
}
int best_path(int N, int K, int H[][2], int L[]) {
	n = N, k = K;
	iloop(0, n-1) {
		adj[H[i][0]].push_back({L[i], H[i][1]});
		adj[H[i][1]].push_back({L[i], H[i][0]});
	}
	dfs(0, -1);
	return (an == INF ? -1 : an);
}

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