| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 880579 | _KuroNeko_ | Race (IOI11_race) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
// using namespace __gnu_pbds;
// #define ordered_set tree<ll, null_type, less_equal<ll>, rb_tree_tag, tree_order_statistics_node_update>
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
using namespace std;
typedef long long ll;
typedef long double ldb;
typedef vector<int> vi;
typedef vector<long long> vl;
typedef vector<double> vdb;
typedef vector<vector<int>> vvi;
typedef vector<vector<ll>> vvl;
typedef vector<string> vs;
typedef set<int> si;
typedef set<long long> sl;
typedef set<double> sdb;
typedef set<string> ss;
typedef set<char> sc;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define ftb(i, a, b) for (int i = a, _b = b; i <= _b; ++i)
#define ft(i, a, b) for (int i = a, _b = b; i < _b; ++i)
#define fgb(i, a, b) for (int i = a, _b = b; i >= _b; --i)
#define fg(i, a, b) for (int i = a, _b = b; i > _b; --i)
#define endl "\n"
const int N = 2 * 1e5;
const int K = 1e6;
int subtree[N + 1];
int dis[K + 1];
bool check[N + 1];
vector<pii> adj[N + 1];
int sz = 0;
void find_subtree(int node, int parent) {
subtree[node] = 1;
for (pii it : adj[node]) {
if (it.first != parent && !check[it.first]) {
find_subtree(it.first, node);
subtree[node] += subtree[it.first];
}
}
}
int centroid(int node, int parent) {
for (pii it : adj[node]) {
if (it.first != parent && !check[it.first]) {
if (subtree[it.first] > sz / 2) {
return centroid(it.first, node);
}
}
}
return node;
}
void dfs(int node, int type, int parent, int depth, int length, int k, int& ans) {
if (length > k) return;
if (type == 3) {
dis[length] = 1e9;
for (pii it : adj[node]) {
if (it.first != parent && !check[it.first]) {
dfs(it.first, type, node, depth + 1, length + it.second, k, ans);
}
}
}
else if (type == 2) {
dis[length] = min(dis[length], depth);
for (pii it : adj[node]) {
if (it.first != parent && !check[it.first]) {
dfs(it.first, type, node, depth + 1, length + it.second, k, ans);
}
}
}
else {
ans = min(ans, depth + dis[k - length]);
for (pii it : adj[node]) {
if (it.first != parent && !check[it.first]) {
dfs(it.first, type, node, depth + 1, length + it.second, k, ans);
}
}
}
}
void solve(int i, int& ans, int k) {
find_subtree(i, -1);
sz = subtree[i];
int node = centroid(i, -1);
check[node] = true;
for (pii it : adj[node]) {
dfs(it.first, 1, -1, 0, 0, k, ans);
dfs(it.first, 2, -1, 0, 0, k, ans);
}
dfs(node, 3, -1, 0, 0, k, ans);
for (pii it : adj[node]) {
if (!check[it.first]) solve(it.first, ans, k);
}
}
int best_part(int n, int k, vvi& h, vi& l) {
memset(dis, 0, sizeof(dis));
ft(i, 0, n - 1) {
adj[h[i][0]].push_back({ h[i][1],l[i] });
adj[h[i][1]].push_back({ h[i][0],l[i] });
}
int ans = 1e9;
solve(0, ans, k);
if (ans == 1e9) ans = -1;
return ans;
}