QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#187932 | #7103. Red Black Tree | Feet_McYeet | RE | 32ms | 223004kb | C++20 | 4.6kb | 2023-09-25 06:41:13 | 2023-09-25 06:41:14 |
Judging History
answer
#include <iostream>
#include <cmath>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <array>
#include <iterator>
#include <algorithm>
// #include <bit>
#include <numeric>
#include <iomanip>
using namespace std;
#pragma GCC optimize ("Ofast")
#pragma GCC target ("avx2")
#define el << '\n'
#define nl cout << '\n'
#define cina(a,n) for (int i=0; i<n; i++) cin >> a[i]
#define ll long long
#define spc << ' '
#define forn(i,n) for (int i=0; i<n; i++)
#define forl(i,s,e) for (int i=s; i<e; i++)
#define pb push_back
#define ansyes cout << "YES\n"
#define ansno cout << "NO\n"
#define fi first
#define se second
#define pii pair<int, int>
#define pll pair<long long, long long>
#define pss pair<short, short>
#define MAX *max_element
#define MIN *min_element
#define rsz resize
#define sz(x) ((int) x.size())
#define all(x) x.begin(), x.end()
#define bsi(x, v) (int) (lower_bound(x.begin(), x.end(), v) - x.begin());
const int inf = 1000000000;
const ll inf2 = 4000000000000000000;
int lg(int k) {
return 32-__builtin_clz(k);
}
const int MAXN = 1000005;
int n;
bool r[MAXN];
vector<pii> adj[MAXN];
vector<int> etd;
int tin[MAXN];
int dep[MAXN];
int ti;
void et(int cn, int pn, int d) {
tin[cn] = ti;
dep[cn] = d;
etd.pb(cn);
ti++;
for (pii i : adj[cn]) {
if (i.fi == pn) continue;
et(i.fi, cn, d+1);
etd.pb(cn);
ti++;
}
}
vector<int> spd[4*MAXN];
vector<int> spi[4*MAXN];
void gst() {
int m = sz(etd);
forn(i,m) {
spi[i].rsz(lg(m-i));
spd[i].rsz(lg(m-i));
spi[i][0]=etd[i];
spd[i][0]=dep[etd[i]];
}
for (int i = m-1; i>=0; i--) {
forl(js, 1, lg(m-i)) {
int l2 = i + (1<<(js-1));
if (spd[i][js-1] < spd[l2][js-1]) {
spd[i][js] = spd[i][js-1];
spi[i][js] = spi[i][js-1];
}
else {
spd[i][js] = spd[l2][js-1];
spi[i][js] = spi[l2][js-1];
}
}
}
// for (int js = 1; (1<<js) <= m; js++) {
// forn(i, m-(1<<js)) {
// int l2 = i + (1<<(js-1));
// if (spd[i][js-1] < spd[l2][js-1]) {
// spd[i][js] = spd[i][js-1];
// spi[i][js] = spi[i][js-1];
// }
// else {
// spd[i][js] = spd[l2][js-1];
// spi[i][js] = spi[l2][js-1];
// }
// }
// }
}
int lca(int a, int b) {
// cout << a spc << b << endl;
a = tin[a];
b = tin[b];
if (a>b) swap(a,b);
int d = lg(b-a)-1;
if (spd[a][d] < spd[b-(1<<d)+1][d]) return spi[a][d];
return spi[b-(1<<d)+1][d];
}
ll d[MAXN];
int dtr[MAXN];
ll ad[MAXN];
void dfs(int cn, int pn, ll de, int ud, ll td) {
if (r[cn]) {
de = 0;
ud = 0;
}
d[cn] = de;
dtr[cn] = ud;
ad[cn] = td;
for (pii i : adj[cn]) {
if (i.fi == pn) continue;
dfs(i.fi, cn, de+i.se, ud+1, td+i.se);
}
}
int t;
ll query (int qs) {
pair<ll, int> v[qs];
forn(i,qs) {
cin >> v[i].se;
v[i].se--;
v[i].fi = d[v[i].se];
}
if (qs == 1) return 0;
sort(v,v+qs);
// forn(i,qs) cout << v[i].se spc << v[i].fi el;
ll ans = v[qs-2].fi;
int l = v[qs-1].se;
for (int i = qs-2; i>0; i--) {
l = lca(l, v[i].se);
// if (t==521) return qs;
ans = min(ans, max(ad[v[qs-1].se] - ad[l], v[i-1].fi));
}
// cout << 'a' << endl;
l = lca(v[0].se, l);
// cout << 'b' << endl;
ans = min(ans, ad[v[qs-1].se] - ad[l]);
return ans;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> t;
while (t--) {
etd.clear();
ti = 0;
int m, q; cin >> n >> m >> q;
forn(i,2*n) {
r[i] = false;
adj[i].clear();
d[i] = 0;
dtr[i] = 0;
ad[i] = 0;
tin[i] = 0;
dep[i] = 0;
}
forn(i,8*n) {
spd[i].clear();
spi[i].clear();
}
forn(i,m) {
int a; cin >> a; a--;
r[a] = true;
}
forn(i,n-1) {
int u, v, w; cin >> u >> v >> w;
u--; v--;
adj[u].pb({v,w});
adj[v].pb({u,w});
}
et(0, -1, 0);
gst();
dfs(0, -1, 0, 0, 0);
forn(qn, q) {
int qt; cin >> qt;
cout << query(qt) << endl;
}
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 32ms
memory: 223004kb
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: -100
Runtime Error
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...