Submission #1080951

#	Time	Username	Problem	Language	Result	Execution time	Memory
1080951		duduFreire	Race (IOI11_race)	C++17	100 / 100	1360 ms	82856 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;

/*

*/

ll k;
struct Centroid {
	vector<vector<pii>> g;
	ll rt, n;
	vi rmv, ssz, par;
	ll ans=oo;

	Centroid(vector<vector<pii>> ag, ll art) : g(ag), rt(art), n(g.size()), rmv(n,0), ssz(n,0), par(n,0) {
		centroid_tree(art);
	} 
	 
	ll sizes(ll a, ll p=-1) {
		ll ans=1;
		for(auto&[b,w]:g[a]) {
			if (b == p or rmv[b]) continue;
			ans+=sizes(b,a);
		}
		return ssz[a]=ans;
	}
	 
	void calcdists(ll a, ll d, ll p, vi& dists) {
		dists[d]++;
		for(auto&[b,w] : g[a]) {
			if (rmv[b] or b==p) continue;
			calcdists(b, d+1, a,dists);
		}
	}	
 
	ll centroid(ll a, ll tsize, ll p=-1) {
		for(auto&[b,w]:g[a]) {
			if (rmv[b] or b==p) continue;
			if (ssz[b] * 2 > tsize) return centroid(b,tsize, a);
		}
		return a;
	}
	void centroid_tree(ll a, ll p=-1) {
		ll c=centroid(a, sizes(a));
	 
		rmv[c]=true;
		par[c]=p;
	 
		solvesub(c); 
	 
		for(auto&[b,w] : g[c]) {
			if (rmv[b]) continue;
			centroid_tree(b, c);
		}
	}

	// do not visit removed guys (if rmv[b] continue)
	void solvesub(ll a) {
		map<ll,ll> best, rbest;
		auto dfs=[&](auto self, ll a, ll sum, ll h, ll p) -> void {
			if (sum <= k) {
				if (!rbest.count(sum) or rbest[sum] > h) rbest[sum]=h;
			}
			for (auto [b,w] : g[a]) if (!rmv[b] and b!=p) {
				self(self,b,sum+w,h+1,a);
			}
		};

		best[0]=0;
		for (auto& [b,w] : g[a]) if (!rmv[b]) {
			dfs(dfs, b, w, 1, a);	
			
			for (auto [val, h] : rbest) {
				if (best.count(k-val)) {
					ans=min(ans, best[k-val]+h);
				}
			}
			for (auto [val, h] : rbest)
				if (!best.count(val) or best[val] > h) best[val]=h;

			map<ll,ll> gbg; swap(rbest, gbg);
		}
	}
};


int best_path(int n, int ak, int h[][2], int l[]) {
	k=ak;
	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]);
	}

	Centroid centroid(g, 0);
	return centroid.ans == oo ? -1 : centroid.ans;
}

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