| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 998332 |
2024-06-13T15:49:42 Z |
Nailuj_217 |
Race (IOI11_race) |
C++17 |
|
3 ms |
13660 KB |
#include <bits/stdc++.h>
#define l long long
using namespace std;
#ifdef EVAL
#include "race.h"
#else
#include "grader.cpp"
#endif
const l LEN = 300005;
array<vector<pair<l, l>>, LEN> adj;
array<bool, LEN> processed;
array<l, LEN> subset;
l best;
l subsetsize(l n, l p = -1) {
l sum = 1;
for (auto [a, b]: adj[n]) {
if (!processed[a] && a != p) sum += subsetsize(a, n);
}
return subset[n] = sum;
}
l find_centroid(l n, l s, l p = -1) {
for (auto [a, b]: adj[n]) {
if (subset[a] > s/2 && a != p && !processed[a]) return find_centroid(a, s, n);
}
return n;
}
void explore_branch(l n, map<l, l>* branch, l k, l maxk, l c = 1, l p = -1) {
if (k > maxk) return;
if (branch->find(k) != branch->end()) (*branch)[k] = min((*branch)[k], c);
else branch->insert({k, c});
for (auto [a, b]: adj[n]) {
if (processed[a] || a == p) continue;
explore_branch(a, branch, k+b, maxk, c+1, n);
}
return;
}
l central_decomposition(l n, l k) {
l centroid = find_centroid(n, subsetsize(n));
processed[centroid] = true;
// try unordered if performance problems
map<l, l> full;
map<l, l> branch;
for (auto [a, b]: adj[centroid]) {
if (processed[a]) continue;
explore_branch(a, &branch, b, k);
if (branch.size() > full.size()) swap(branch, full);
for (auto [key, val]: branch) {
if (val == k) best = min(best, val);
else if (full.find(k-key) != full.end()) best = min(best, val + full[k-key]);
}
full.merge(branch);
branch.clear();
}
for (auto [a, b]: adj[centroid])
if (!processed[a])
central_decomposition(a, k);
return best;
}
int best_path(int N, int K, int H[][2], int L[]) {
adj.fill({});
processed.fill(0);
best = 1LL<<60;
for (int i = 0; i < N-1; i++) {
adj[H[i][0]].push_back({H[i][1], L[i]});
adj[H[i][1]].push_back({H[i][0], L[i]});
}
central_decomposition(1, K);
if (best == (1LL<<60)) return -1;
return best;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
13656 KB |
Output is correct |
| 2 |
Correct |
2 ms |
13660 KB |
Output is correct |
| 3 |
Correct |
2 ms |
13660 KB |
Output is correct |
| 4 |
Correct |
3 ms |
13660 KB |
Output is correct |
| 5 |
Correct |
2 ms |
13660 KB |
Output is correct |
| 6 |
Correct |
2 ms |
13660 KB |
Output is correct |
| 7 |
Correct |
2 ms |
13660 KB |
Output is correct |
| 8 |
Incorrect |
2 ms |
13660 KB |
Output isn't correct |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
13656 KB |
Output is correct |
| 2 |
Correct |
2 ms |
13660 KB |
Output is correct |
| 3 |
Correct |
2 ms |
13660 KB |
Output is correct |
| 4 |
Correct |
3 ms |
13660 KB |
Output is correct |
| 5 |
Correct |
2 ms |
13660 KB |
Output is correct |
| 6 |
Correct |
2 ms |
13660 KB |
Output is correct |
| 7 |
Correct |
2 ms |
13660 KB |
Output is correct |
| 8 |
Incorrect |
2 ms |
13660 KB |
Output isn't correct |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
13656 KB |
Output is correct |
| 2 |
Correct |
2 ms |
13660 KB |
Output is correct |
| 3 |
Correct |
2 ms |
13660 KB |
Output is correct |
| 4 |
Correct |
3 ms |
13660 KB |
Output is correct |
| 5 |
Correct |
2 ms |
13660 KB |
Output is correct |
| 6 |
Correct |
2 ms |
13660 KB |
Output is correct |
| 7 |
Correct |
2 ms |
13660 KB |
Output is correct |
| 8 |
Incorrect |
2 ms |
13660 KB |
Output isn't correct |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
13656 KB |
Output is correct |
| 2 |
Correct |
2 ms |
13660 KB |
Output is correct |
| 3 |
Correct |
2 ms |
13660 KB |
Output is correct |
| 4 |
Correct |
3 ms |
13660 KB |
Output is correct |
| 5 |
Correct |
2 ms |
13660 KB |
Output is correct |
| 6 |
Correct |
2 ms |
13660 KB |
Output is correct |
| 7 |
Correct |
2 ms |
13660 KB |
Output is correct |
| 8 |
Incorrect |
2 ms |
13660 KB |
Output isn't correct |
| 9 |
Halted |
0 ms |
0 KB |
- |
