oj.uz

Submission #203913

# Submission time Handle Problem Language Result Execution time Memory
203913 2020-02-23T02:41:38 Z kimjg1119 Race (IOI11_race) C++17
0 / 100
 8 ms 5112 KB 
#include <bits/stdc++.h>
#include <random>
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
#define endl "\n"
#define ends " "
#define pb(x) push_back(x)
#define sz(x) ((int)(x).size())
#define fio() ios_base::sync_with_stdio(0); cin.tie(0)

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> tpi;
typedef tuple<ll, ll, ll> tpl;

const ll MOD = 1000000007;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
const double pi = acos(-1);
const double eps = 1e-10;

int n, k, ans = INF;
int siz[202020], chk[202020];
vector<pii> adj[202020];

int find_size(int x, int par) {
	int ret = 1;
	for (auto th : adj[x]) {
		if (th.first == par || chk[th.first]) continue;
		ret += find_size(th.first, x);
	}
	return siz[x] = ret;
}

int get_cent(int x, int par, int cnt) {
	for (auto th : adj[x]) {
		if (th.first == par || chk[th.first]) continue;
		if (siz[th.first] > cnt / 2) return get_cent(th.first, x, cnt);
	}
	return x;
}

vector<pii> all_path;
void find_path(int x, int par, int len, int dep) {
	if (len > k) return;
	all_path.emplace_back(len, dep);
	for (auto th : adj[x]) {
		if (th.first == par || chk[th.first]) continue;
		find_path(th.first, x, len + th.second, dep + 1);
	}
}

void solve(int x) {
	int cal = find_size(x, x);
	int cent = get_cent(x, x, cal);

	// cent를 지나는 경로들
	all_path.clear();
	find_path(cent, cent, 0, 0);
	sort(all(all_path));

	vector<pii> path;
	for (auto hr : all_path) {
		if (!path.empty() && path.back().first == hr.first) continue;
		path.push_back(hr);
	}

	int ri = sz(path) - 1;
	for (int i = 0; i < ri; i++) {
		int left = k - path[i].first;
		while (ri > i + 1 && path[ri].first > left) ri--;
		if (path[ri].first == left)
			ans = min(ans, path[i].second + path[ri].second);
	}

	// cent를 지나지 않는 경로들
	chk[cent] = 1;
	for (auto th : adj[cent]) {
		int thv = th.first;
		if (chk[thv]) continue;
		solve(thv);
	}
}

int best_path(int N, int K, int H[][2], int L[]) {
	n = N; k = K;
	for (int i = 0; i < n - 1; i++) {
		int a = H[i][0], b = H[i][1];
		adj[a].emplace_back(b, L[i]);
		adj[b].emplace_back(a, L[i]);
	}
	solve(0);
	if (ans == INF) return -1;
	else return ans;
}

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 5112 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 5112 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 5112 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 5112 KB Output isn't correct
2 Halted 0 ms 0 KB -