| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 986644 |
2024-05-21T01:24:22 Z |
happypotato |
Race (IOI11_race) |
C++17 |
|
6 ms |
16728 KB |
#include "race.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int, int>
#define ff first
#define ss second
#define pb push_back
const int mxN = 2e5 + 10;
vector<pii> adj[mxN];
bool vis[mxN];
int subt[mxN], dep[mxN];
int centpar[mxN];
ll path[mxN];
map<ll, vector<pii>> mp[mxN];
void dfs_subt(int u, int par) {
subt[u] = 1;
for (pii v : adj[u]) {
if (v.ff == par || vis[v.ff]) continue;
dfs_subt(v.ff, u);
subt[u] += subt[v.ff];
}
}
int dfs_cent(int u, int par, int tar) {
for (pii v : adj[u]) {
if (v.ff == par || vis[v.ff]) continue;
if (subt[v.ff] * 2 > tar) return dfs_cent(v.ff, u, tar);
}
return u;
}
void dfs_decomp(int u = 1, int par = 0, int depth = 1) {
dfs_subt(u, par);
u = dfs_cent(u, par, subt[u]);
dep[u] = depth;
centpar[u] = par;
vis[u] = true;
for (pii v : adj[u]) {
if (v.ff == par || vis[v.ff]) continue;
dfs_decomp(v.ff, u, depth + 1);
}
}
void dfs_path(int u = 1, int par = 0, ll cur = 0) {
path[u] = cur;
for (pii v : adj[u]) {
if (v.ff == par) continue;
dfs_path(v.ff, u, cur + v.ss);
}
}
int best_path(int n, int k, int H[][2], int L[]) {
for (int i = 0; i < n; i++) {
H[i][0]++; H[i][1]++;
adj[H[i][0]].pb({H[i][1], L[i]});
adj[H[i][1]].pb({H[i][0], L[i]});
}
dfs_decomp();
dfs_path();
vector<int> order;
for (int i = 1; i <= n; i++) order.pb(i);
sort(order.begin(), order.end(), [&](int x, int y) {
return dep[x] > dep[y];
});
int ans = n;
for (int x : order) {
// cerr << x << ":\n";
// for (auto it = mp[x].begin(); it != mp[x].end(); ++it) {
// cerr << it->ff << " | ";
// for (pii cur : it->ss) {
// cerr << "{" << cur.ff << ", " << cur.ss << "} ";
// }
// cerr << endl;
// }
// cerr << "end of " << x << endl;
for (auto it = mp[x].begin(); it != mp[x].end(); ++it) {
sort(it->ss.begin(), it->ss.end());
}
if (mp[x].find(path[x] + k) != mp[x].end()) {
ans = min(ans, mp[x][path[x] + k].front().ff - dep[x]);
}
for (auto it = mp[x].begin(); it != mp[x].end(); ++it) {
ll tar = path[x] * 2 - it->ff + k;
if (mp[x].find(tar) != mp[x].end()) {
for (pii cur : mp[x][tar]) {
if (cur.ss == it->ss.front().ss) continue;
ans = min(ans, cur.ss + it->ss.front().ff - 2 * dep[x]);
break;
}
}
}
if (x == 1) break;
mp[x][path[x]] = {{dep[x], x}};
for (auto it = mp[x].begin(); it != mp[x].end(); ++it) {
mp[centpar[x]][it->ff].pb({it->ss.front().ff, x});
}
}
return (ans == n ? -1 : ans);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
16728 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
16728 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
16728 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
16728 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
