Submission #212650

#	Time	Username	Problem	Language	Result	Execution time	Memory
212650		Dan13llljws	Race (IOI11_race)	C++14	100 / 100	1385 ms	38776 KiB

race

#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define sp ' '
#define nl '\n'
void sc(){}template<class T,class...A>void sc(T&t,A&...a){cin>>t,sc(a...);}
void pr(){}template<class T,class...A>void pr(T t,A...a){cout<<t,pr(a...);}
#define ms(x, y) memset(x, y, sizeof(x))
#define sz(x) (int)(x.size())
#define af(x) x.begin(), x.end()
#define mp make_pair
#define pb push_back
#define f first
#define s second
const int mod = 1e9 + 7, base = 131;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
const int MM = 2e5 + 5;
int M, w[MM], ans = INF; bool vis[MM];
vector<pii> adj[MM];
map<int, int> cnt, tmp;
void get_weight(int src, int par){
	w[src] = 1;
	for (auto v : adj[src]){
		if (v.s == par || vis[v.s]) continue;
		get_weight(v.s, src);
		w[src] += w[v.s];
	}
}
int get_cent(int src, int par, int wt){
	for (auto v : adj[src]){
		if (v.s == par || vis[v.s]) continue;
		if (w[v.s] * 2 > wt) return get_cent(v.s, src, wt);
	}
	return  src;
}
void proc_subtree(int src, int par, int d, int dep){
    if (d > M) return;
	if (d == M) ans = min(ans, dep);
	if (!tmp.count(d)) tmp[d] = dep;
	else tmp[d] = min(tmp[d], dep);
	if (cnt.count(M - d)) ans = min(ans, cnt[M - d] + dep);
	for (auto v : adj[src]){
		if (v.s == par || vis[v.s]) continue;
		proc_subtree(v.s, src, d + v.f, dep + 1);
	}
}
void get_ans(int src){
	cnt.clear(); 
	for (auto v : adj[src]){
		if (vis[v.s]) continue;
		tmp.clear();
		proc_subtree(v.s, src, v.f, 1);
		for (auto m : tmp){
			if (!cnt.count(m.f)) cnt[m.f] = m.s;
			else cnt[m.f] = min(cnt[m.f], m.s);
		}
	}
}
void decomp(int src){
	vis[src] = 1;
	get_ans(src);
	for (auto v : adj[src]){
		if (vis[v.s]) continue;
		get_weight(v.s, src);
		decomp(get_cent(v.s, src, w[v.s]));
	}
}
int best_path(int N, int K, int H[][2], int L[]){
	M = K;
	for (int i = 0; i < N - 1; i++){
		int a = H[i][0], b = H[i][1], c = L[i];
		adj[a].pb(mp(c, b)); adj[b].pb(mp(c, a));
	}
	get_weight(1, 1);
	decomp(get_cent(1, 1, N));
	return ans == INF ? -1 : ans;
}

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