Submission #320003

#	Time	Username	Problem	Language	Result	Execution time	Memory
320003		shrek12357	Race (IOI11_race)	C++14	0 / 100	6 ms	8940 KiB

race

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <map>
#include <set>
#include <climits>
#include <cmath>
#include <fstream>
#include <queue>
#include <stack>
#include <bitset>
#include "race.h"
using namespace std;
#define ll long long
//cin.tie(0);ios_base::sync_with_stdio(0); 
 
const int MAXN = 2 * 1e5 + 5;
const int MAXV = 1e6 + 5;
const int INF = 1e9;
 
int n;
ll k;
int h[MAXN][2];
int l[MAXN];
vector<pair<int, int>> adjList[MAXN];
bool found[MAXN];
int idx = -1;
int s[MAXN];
int vals[MAXV];
set<int> used;
int ans = INF;
int tot = 0;
queue<pair<int, int>> add;
 
void cnt(int src, int p) {
	tot++;
	for (auto i : adjList[src]) {
		if (i.first == p || found[i.first]) {
			continue;
		}
		cnt(i.first, src);
	}
}
 
void centroid(int src, int p) {
	s[src] = 1;
	int mxVal = 0;
	for (auto i : adjList[src]) {
		if (i.first == p || found[i.first]) {
			continue;
		}
		centroid(i.first, src);
		s[src] += s[i.first];
		mxVal = max(mxVal, s[i.first]);
	}
	if (mxVal <= tot / 2 && tot - s[src] <= tot / 2) {
		idx = src;
	}
}
 
void dfs1(int src, int p, int cur, int paths) {
	for (auto i : adjList[src]) {
		if (i.first == p || found[i.first]) {
			continue;
		}
		int nxt = cur + i.second;
		if (nxt > k) {
			continue;
		}
		ans = min(ans, vals[k - nxt] + paths + 1);
		add.push({ nxt, paths + 1 });
		dfs1(i.first, src, nxt, paths + 1);
		if (src == idx) {
			while (add.size() > 0) {
				int rn = add.front().first;
				vals[rn] = min(vals[rn], add.front().second);
				used.insert(rn);
				add.pop();
			}
		}
	}
}
 
void dfs(int src, int p) {
	idx = -1;
	tot = 0;
	cnt(src, p);
	centroid(src, p);
	if (tot == 1) {
		return;
	}
	found[idx] = true;
	dfs1(idx, idx, 0, 0);
	for (auto i : used) {
		vals[i] = INF;
	}
	used.clear();
	for (auto i : adjList[idx]) {
		if (i.first == p || found[i.first]) {
			continue;
		}
		dfs(i.first, src);
	}
}
 
int best_path(int n, int k, int h[][2], int l[]) {
	for (int i = 0; i < n - 1; i++) {
		adjList[h[i][0]].push_back({ h[i][1], l[i] });
		adjList[h[i][1]].push_back({ h[i][0], l[i] });
	}
	for (int i = 0; i < MAXV; i++) {
		vals[i] = INF;
	}
	vals[0] = 0;
	dfs(0, 0);
	if (ans > n) {
		return -1;
	}
	return ans;
}

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