Submission #198976

#	Time	Username	Problem	Language	Result	Execution time	Memory
198976		godwind	Race (IOI11_race)	C++14	0 / 100	10 ms	5116 KiB

race

// O O O O O O O O O O O O O O O OO O OO O OO O O O TTCH O TTTCH O TTTCH O O O O
#pragma GCC optimize("Ofast")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,popcnt,abm,mmx")
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <stdio.h>
#include <cstdio>
#include <math.h>
#include <cmath>
#include <string>
#include <cstring>
#include <queue>
#include <deque>
#include <random>
#include <iomanip>
#include <bitset>
#include <cassert>
// #include "grader.h"
 
using namespace std;

#define y1 y11
#define double long double
#define less less228
#define left left228
#define right right228
#define list list228

template<typename T> void uin(T &a, T b) {
    if (b < a) a = b;
}
template<typename T> void uax(T &a, T b) {
    if (b > a) a = b;
}
 

const int MAXN = 200 * 1000 + 228;
const int INF = 1e9 + 228;

int n, k;
vector< pair<int, int> > g[MAXN];
int sz[MAXN];
bool blocked[MAXN];
int allsz = 0;
int answer = INF;

void szdfs(int v, int par = -1) {
	sz[v] = 1;
	++allsz;
	for (pair<int, int> go : g[v]) {
		if (go.first == par || blocked[go.first]) continue;
		szdfs(go.first, v);
		sz[v] += sz[go.first];
	}
}

int centroid = 0;

void ffc(int v, int par = -1) {
	bool goin = 0;
	for (pair<int, int> go : g[v]) {
		if (go.first == par || blocked[go.first]) continue;
		if (sz[go.first] > allsz / 2) {
			ffc(go.first, v);
			goin = 1;
		}
	}
	if (sz[v] >= allsz / 2 && !goin) centroid = v;
}

int FindCentroid(int v) {
	centroid = allsz = 0;
	szdfs(v);
	ffc(v);
	return centroid;
}

int minh[1000 * 1000 + 228];
int h[MAXN];
int w[MAXN];

void godfs(int v, int par, int W) {
	w[v] = W;
	h[v] = h[par] + 1;
	if (w[v] <= k) {
		uin(answer, h[v] + minh[k - w[v]]);
	}
	for (pair<int, int> go : g[v]) {
		if (go.first == par || blocked[go.first]) continue;
		godfs(go.first, v, W + go.second);
	}
}

void update_dfs(int v, int par) {
	uin(minh[w[v]], h[v]);
	for (pair<int, int> go : g[v]) {
		if (go.first == par || blocked[go.first]) continue;
		update_dfs(go.first, v);
	}
}
void update_back(int v, int par) {
	minh[w[v]] = INF;
	for (pair<int, int> go : g[v]) {
		if (go.first == par || blocked[go.first]) continue;
		update_back(go.first, v);
	}
}

void solve(int c) {
	minh[0] = 0;
	h[c] = w[c] = 0;
	for (pair<int, int> go : g[c]) {
		if (!blocked[go.first]) {
			godfs(go.first, c, go.second);
			update_dfs(go.first, c);
		}
	}
	for (pair<int, int> go : g[c]) {
		if (!blocked[go.first]) {
			update_back(go.first, c);
		}
	}
}

void build(int v) {
	int c = FindCentroid(v);
	blocked[c] = 1;
	solve(c);
	for (pair<int, int> go : g[v]) {
		int to = go.first;
		if (!blocked[to]) {
			build(to);
		}
	}
}

void dfs(int v, int par = -1, int w = 0, int l = 0) {
	if (w == k) uin(answer, l);
	for (pair<int, int> go : g[v]) {
		int to = go.first, ww = go.second;
		if (to == par) continue;
		dfs(to, v, w + ww, l + 1);
	}
}

int best_path(int N, int K, int H[][2], int L[]){
	n = N;
	k = K;
	for (int i = 0; i <= k; ++i) {
		minh[i] = INF;
	}
	for (int i = 0; i < n - 1; ++i) {
		++H[i][0], ++H[i][1];
		g[H[i][0]].emplace_back(H[i][1], L[i]);
		g[H[i][1]].emplace_back(H[i][0], L[i]);
	}
	answer = INF;
	for (int i = 1; i <= n; ++i) {
		dfs(i);
	}
	// answer = INF;
	// build(1);
	// if (answer == INF) answer = -1;
	return answer;
}

// int H[100][2];
// int L[100];

// signed main() {
// 	int nn, kk;
// 	cin >> nn >> kk;
// 	for (int i = 0; i < nn - 1; ++i) {
// 		cin >> H[i][0] >> H[i][1] >> L[i];
// 	}
// 	cout << best_path(nn, kk, H, L) << '\n';
// }

/*
4 3
0 1 1
1 2 2
1 3 4

11 12
0 1 3
0 2 4
2 3 5
3 4 4
4 5 6
0 6 3
6 7 2
6 8 5
8 9 6
8 10 7
*/

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