Submission #1081039

#	Time	Username	Problem	Language	Result	Execution time	Memory
1081039		duduFreire	Race (IOI11_race)	C++17	100 / 100	439 ms	121684 KiB

race

#include <bits/stdc++.h>

#define ll long long
#define endl '\n'
#define pb push_back
#define eb emplace_back
#define all(x) (x).begin(), (x).end()
#define rep(i, a, b) for(ll i=(ll)(a);i < (ll)(b);i++)
#define pii pair<ll, ll>
#define vi vector<ll>
#define vvi vector<vi>
#define sz(x) ((ll)(x).size())

#ifdef LOCAL
#define debug(var) cerr << #var << ": " << var << endl
#else
#define debug(var)
#endif


using namespace std;

template<class T, class U> auto &operator>>(istream &is, pair<T, U> &p) { return is >> p.first >> p.second; }
template<class T, class U> auto &operator<<(ostream &os, pair<T, U> const& p) { return os << '{' << p.first << ' ' << p.second << '}'; }
const auto ES = "", SEP = " ";
template<class T> auto &operator>>(istream& is, vector<T> &c) { for (auto &x : c) is >> x; return is; }
template<class T> auto &operator<<(ostream& os, vector<T> const &c) { auto sep = ES; for (auto x : c) os << sep << x, sep = SEP; return os; }
template<class T> auto &operator<<(ostream& os, set<T> const &c) { auto sep = ES; for (auto x : c) os << sep << x, sep = SEP; return os; }
template<class T> auto &operator<<(ostream& os, multiset<T> const &c) { auto sep = ES; for (auto x : c) os << sep << x, sep = SEP; return os; }
template<class T> auto &operator<<(ostream& os, unordered_set<T> const &c) { auto sep = ES; for (auto x : c) os << sep << x, sep = SEP; return os; }
template<class T> auto &operator<<(ostream& os, deque<T> const &c) { auto sep = ES; for (auto x : c) os << sep << x, sep = SEP; return os; }
template<class K, class V> auto &operator<<(ostream& os, map<K,V> const &c) { auto sep = ES; for (auto x : c) os << sep << x, sep = SEP; return os; }
template<class K, class V> auto &operator<<(ostream& os, unordered_map<K,V> const &c) { auto sep = ES; for (auto x : c) os << sep << x, sep = SEP; return os; }

ll ceil(ll a, ll b) {
	return (a+b-1)/b;
}

constexpr ll MAX=2e5;
constexpr ll MOD=1e9+7;
constexpr ll oo=0x3f3f3f3f3f3f3f3f;

/*

*/

struct Info {
	map<ll, ll> best;
	ll vh, vw;

	Info() : vh(0), vw(0) {best[0]=0;}

	ll geth(ll val) {
		ll tval=val-vw;
		return best.count(tval) ? best[tval] + vh : oo;
	}

	void setmin(ll val, ll h) {
		ll tval=val-vw;
		if (!best.count(tval) or best[tval] + vh > h) best[tval]=h-vh;
	}
};


int best_path(int n, int k, int h[][2], int l[]) {
	vector<vector<pii>> g(n);
	rep(i,0,n-1) {
		g[h[i][0]].eb(h[i][1],l[i]);
		g[h[i][1]].eb(h[i][0],l[i]);
	}

	#warning change ll to ll
	ll ans=oo;
	vector<Info> infos(n);
	auto dfs=[&](auto self, ll a, ll p) -> void{
		Info cinfo;
		for (auto [b,w] : g[a])	if (b!=p) {
			self(self, b, a);
			infos[b].vw += w;
			infos[b].vh++;

			if (sz(infos[b].best) > sz(cinfo.best)) swap(infos[b], cinfo);
			
			ll& vw=infos[b].vw;
			ll& vh=infos[b].vh;
			for (auto [val, h] : infos[b].best) 
				ans=min(ans, cinfo.geth(k-(val+vw)) + h+vh);
			
			for (auto [val,h] : infos[b].best)
				cinfo.setmin(val+vw, h+vh);
		}
		swap(cinfo, infos[a]);
	};
	dfs(dfs,0,-1);
	return ans==oo ? -1 : ans;
}

Compilation message (stderr)

race.cpp:72:3: warning: #warning change ll to ll [-Wcpp]
   72 |  #warning change ll to ll
      |   ^~~~~~~

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