Submission #199209

#	Time	Username	Problem	Language	Result	Execution time	Memory
199209		dennisstar	Race (IOI11_race)	C++17	100 / 100	1172 ms	35576 KiB

race

#include <bits/stdc++.h>
#define fi first
#define se second
#define em emplace
#define eb emplace_back
#define sq(X) ((X)*(X))
#define all(V) (V).begin(), (V).end()
#define chk_init memset(chk, 0, sizeof(chk))
#define unq(V) (V).erase(unique(all(V)), (V).end())
using namespace std;
typedef long long ll;
typedef vector<ll> vlm;
typedef vector<int> vim;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
const int INF=(1<<30);
#include "race.h"

int N, K;
vector<pii> adj[200010];
int fin[200010], sz[200010], im, ans;
set<pii> S;
pii vis[200010]; int tp;

void subsz(int now, int par) {
	sz[now]=1;
	for (auto &i:adj[now]) if (i.fi!=par&&!fin[i.fi]) {
		subsz(i.fi, now);
		sz[now]+=sz[i.fi];
	}
}

int get_cent(int now, int par) {
	for (auto &i:adj[now]) if (i.fi!=par&&!fin[i.fi]&&sz[i.fi]>=im/2) return get_cent(i.fi, now);
	return now;
}

void visit(int now, int par, int d, int dep) {
	vis[tp++]=pii(d, dep);
	for (auto &i:adj[now]) if (i.fi!=par&&!fin[i.fi]) visit(i.fi, now, d+i.se, dep+1);
}

void dfs(int now) {
	subsz(now, 0); im=sz[now];
	int cent=get_cent(now, 0); fin[cent]=1;
	S.clear(); set<pii>::iterator it;
	for (auto &i:adj[cent]) if (!fin[i.fi]) {
		tp=0; visit(i.fi, cent, i.se, 1);
		for (int j=0; j<tp; j++) {
			it=S.lower_bound(pii(K-vis[j].fi, 0));
			if (it==S.end()||it->fi!=K-vis[j].fi) continue;
			ans=min(ans, it->se+vis[j].se);
		}
		for (int j=0; j<tp; j++) S.insert(vis[j]);
	}
	it=S.lower_bound(pii(K, 0));
	if (!(it==S.end()||it->fi!=K)) ans=min(ans, it->se);
	for (auto &i:adj[cent]) if (!fin[i.fi]) dfs(i.fi);
}

int best_path(int N_, int K_, int H[][2], int L[]) {
	N=N_; K=K_;
	for (int i=0; i<N-1; i++) adj[H[i][0]+1].eb(H[i][1]+1, L[i]), adj[H[i][1]+1].eb(H[i][0]+1, L[i]);
	ans=INF; dfs(1);
	return ans==INF?-1:ans;
}

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