QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#273808 | #7103. Red Black Tree | ikaurov# | AC ✓ | 1157ms | 42528kb | C++20 | 3.9kb | 2023-12-03 04:21:56 | 2023-12-03 04:21:56 |
Judging History
answer
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define all(arr) (arr).begin(), (arr).end()
#define ll long long
#define ld long double
#define pb push_back
#define sz(x) (int)(x).size()
#define fi first
#define se second
#define endl '\n'
const int N = 1e5 + 20, LOG = 20;
const ll INF = 1e18;
vector<pair<int, ll>> g[N], ng[N];
ll val[N];
int par[N][LOG], tin[N], tout[N], timer, pidx[N], sidx[N], wohoo[N];
ll prefdist[N];
bool red[N], marked[N];
void dfs1(int v, int p, ll dist, int who){
par[v][0] = p;
for (int i = 1; i < LOG; i++) par[v][i] = par[par[v][i - 1]][i - 1];
val[v] = (red[v]? 0 : dist);
wohoo[v] = (red[v]? v : who);
dist = val[v], who = wohoo[v];
tin[v] = timer++;
for (auto [u, w] : g[v]){
if (u == p) continue;
prefdist[u] = prefdist[v] + w;
dfs1(u, v, dist + w, who);
}
tout[v] = timer++;
}
bool is_anc(int u, int v){
return tin[u] <= tin[v] && tin[v] <= tout[u];
}
int lca(int u, int v){
if (is_anc(u, v)) return u;
if (is_anc(v, u)) return v;
for (int i = LOG - 1; i >= 0; i--){
if (!is_anc(par[u][i], v)) u = par[u][i];
}
return par[u][0];
}
ll dist(int u, int v){
return abs(prefdist[u] - prefdist[v]);
}
vector<ll> prefmax, suffmax;
ll curans;
ll maxdist[N], maxcompleted[N];
void dfs2(int v){
maxdist[v] = (marked[v] && !red[v]? 0 : -INF), maxcompleted[v] = 0;
for (auto [u, w] : ng[v]){
dfs2(u);
if (red[v]) maxcompleted[v] = max({maxcompleted[v], maxcompleted[u], maxdist[u] + w});
else maxdist[v] = max(maxdist[v], maxdist[u] + w), maxcompleted[v] = max(maxcompleted[v], maxcompleted[u]);
}
if (red[v]) return;
curans = min(curans,
max({maxcompleted[v], maxdist[v],
pidx[v]? prefmax[pidx[v] - 1] : 0,
sidx[v] == sz(suffmax) - 1? 0 : suffmax[sidx[v] + 1]}));
}
ll subsolve(vector<int> nodes){
for (auto i : nodes) marked[i] = 1;
int n = sz(nodes);
sort(all(nodes), [&] (int i, int j){
return tin[i] < tin[j];
});
for (int i = 1; i < n; i++){
nodes.pb(lca(nodes[i], nodes[i - 1]));
}
nodes.pb(1);
for (int i = 0; i < n; i++){
nodes.pb(wohoo[nodes[i]]);
}
sort(all(nodes), [&] (int i, int j){
return tin[i] < tin[j];
});
nodes.erase(unique(all(nodes)), nodes.end());
vector<int> stk{1};
for (int i = 1; i < sz(nodes); i++){
int v = nodes[i];
while (!is_anc(stk.back(), v)) stk.pop_back();
ng[stk.back()].pb({v, dist(v, stk.back())});
stk.pb(v);
}
n = sz(nodes);
prefmax = suffmax = vector<ll>(n);
for (int i = 0; i < n; i++){
ll cur = (marked[nodes[i]]? val[nodes[i]] : 0);
if (i) prefmax[i] = prefmax[i - 1];
prefmax[i] = max(prefmax[i], cur);
pidx[nodes[i]] = i;
}
sort(all(nodes), [&] (int i, int j){
return tout[i] < tout[j];
});
for (int i = n - 1; i >= 0; i--){
ll cur = (marked[nodes[i]]? val[nodes[i]] : 0);
if (i + 1 < n) suffmax[i] = suffmax[i + 1];
suffmax[i] = max(suffmax[i], cur);
sidx[nodes[i]] = i;
}
curans = 0;
for (auto v : nodes) if (marked[v]) curans += val[v];
dfs2(1);
for (auto v : nodes){
marked[v] = 0;
ng[v].clear();
}
return curans;
}
void solve(){
int n, m, q;
cin >> n >> m >> q;
for (int i = 0; i <= n; i++){
g[i].clear();
ng[i].clear();
red[i] = 0;
}
while (m--){
int x;
cin >> x;
red[x] = 1;
}
for (int i = 1; i < n; i++){
int u, v, w;
cin >> u >> v >> w;
g[u].pb({v, w});
g[v].pb({u, w});
}
timer = 0;
dfs1(1, 1, 0, 0);
while (q--){
int k;
cin >> k;
vector<int> nodes(k);
for (auto &i : nodes) cin >> i;
cout << subsolve(nodes) << endl;
}
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
// cout.precision(20);
int t;
cin >> t;
while (t--){
solve();
}
}
这程序好像有点Bug,我给组数据试试?
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 13540kb
input:
2 12 2 4 1 9 1 2 1 2 3 4 3 4 3 3 5 2 2 6 2 6 7 1 6 8 2 2 9 5 9 10 2 9 11 3 1 12 10 3 3 7 8 4 4 5 7 8 4 7 8 10 11 3 4 5 12 3 2 3 1 2 1 2 1 1 3 1 1 1 2 1 2 3 1 2 3
output:
4 5 3 8 0 0 0
result:
ok 7 lines
Test #2:
score: 0
Accepted
time: 1157ms
memory: 42528kb
input:
522 26 1 3 1 1 4 276455 18 6 49344056 18 25 58172365 19 9 12014251 2 1 15079181 17 1 50011746 8 9 2413085 23 24 23767115 22 2 26151339 26 21 50183935 17 14 16892041 9 26 53389093 1 20 62299200 24 18 56114328 11 2 50160143 6 26 14430542 16 7 32574577 3 16 59227555 3 15 8795685 4 12 5801074 5 20 57457...
output:
148616264 148616264 0 319801028 319801028 255904892 317070839 1265145897 1265145897 1072765445 667742619 455103436 285643094 285643094 285643094 317919339 0 785245841 691421476 605409472 479058444 371688030 303203698 493383271 919185207 910180170 919185207 121535083 181713164 181713164 181713164 181...
result:
ok 577632 lines
Extra Test:
score: 0
Extra Test Passed