QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#225779 | #7103. Red Black Tree | ucup-team992 | AC ✓ | 677ms | 37172kb | C++17 | 4.6kb | 2023-10-25 08:48:35 | 2023-10-25 08:48:36 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define ar array
#define ll long long
typedef int uci;
#define int long long
#define F first
#define S second
typedef complex<double> cd;
seed_seq seq{
(uint64_t) chrono::duration_cast<chrono::nanoseconds>(chrono::high_resolution_clock::now().time_since_epoch()).count(),
(uint64_t) __builtin_ia32_rdtsc(),
(uint64_t) (uintptr_t) make_unique<char>().get()
};
mt19937 rng(seq);
// mt19937_64 lrng(seq);
struct debugger{
template <typename T>
debugger& operator<<(T &a){
#ifdef DEBUG
cerr << a;
#endif
return *this;
}
template <typename T>
debugger& operator<<(T &&a){
#ifdef DEBUG
cerr << a;
#endif
return *this;
}
} deb;
const double PI = acos(-1.0);
const int MAX_N = 1e5 + 1;
const int MOD = 1e9 + 7;
const int INF = 1e9;
const ll LINF = 1e18;
//! function insert
//THINK FIRST, CODE SECOND
//DON'T GET STUCK ON ONE STRATEGY
//CALM DOWNNN FOR ONCE IN YOUR LIFE
//REDUCE
//COUGH E??!?!?!! O.O
//uwu i see you ryan
bool isred[100001];
int dist[100001];
int lift[100001][20];
int cost[100001];
int depth[100001];
void dfs(int v, int p, int c, int d, int de, vector<vector<ar<int, 2>>> &adj){
if(isred[v])
d = 0;
dist[v] = d;
depth[v] = de;
lift[v][0] = p;
cost[v] = c;
for(int i{1}; i < 20; ++i){
lift[v][i] = lift[lift[v][i-1]][i-1];
}
for(auto i : adj[v]){
if(i[0] == p)
continue;
dfs(i[0], v, c+i[1], d+i[1], de+1, adj);
}
}
int goup(int v, int p){
int c{};
while(p){
if(p&1){
v = lift[v][c];
}
p >>= 1;
c++;
}
return v;
}
int lca(int u, int v){
if(depth[u] > depth[v])
swap(u, v);
v = goup(v, depth[v] - depth[u]);
if(u == v)
return u;
for(int i = 19; i >= 0; --i){
if(lift[u][i] != lift[v][i]){
u = lift[u][i];
v = lift[v][i];
}
}
return lift[u][0];
}
void solve() {
int n, m, q;
cin >> n >> m >> q;
for(int i{}; i < n; ++i)
isred[i] = false;
isred[0] = true;
for(int i{}; i < m; ++i){
int t;
cin >> t;
t--;
isred[t] = true;
}
vector<vector<ar<int, 2>>> adj(n);
for(int i{}; i < n-1; ++i){
int u, v;
cin >> u >> v;
int w;
u--, v--;
cin >> w;
adj[u].push_back({v, w});
adj[v].push_back({u, w});
}
dfs(0, 0, 0, 0, 0, adj);
for(int i{}; i < q; ++i){
int k;
cin >> k;
vector<int> a(k);
for(int j{}; j < k; ++j){
cin >> a[j];
a[j]--;
}
sort(a.begin(), a.end(), [&](auto a, auto b){
return dist[a] > dist[b];
});
int best = cost[a[0]];
int lc = a[0];
int mde = cost[a[0]];
for(int j{}; j < k; ++j){
lc = lca(lc, a[j]);
mde = max(mde, cost[a[j]]);
deb << lc << ' '<<mde << ' ' << cost[lc] << '\n';
if(j == k-1){
best = min(best, mde - cost[lc]);
}else{
deb << dist[a[j+1]] << '\n';
best = min(best, max(dist[a[j+1]], mde-cost[lc]));
}
}
cout << best << '\n';
}
}
uci main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
// freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
int tc; cin >> tc;
for (int t = 1; t <= tc; t++) {
// cout << "Case #" << t << ": ";
solve();
}
}
/*
random number generator stuff
num = rng(); gives integer number
num = uniform_int_distribution<int>(a, b)(rng); -> bounds [a, b]
num = uniform_real_distribution<double>(a, b)(rng); -> bounds [a, b)
can also instantiate distributions and call on generator:
uniform_int_distribution<int> thing(a, b);
num = thing(rng);
*/
// struct custom_hash {
// static uint64_t splitmix64(uint64_t x) {
// // http://xorshift.di.unimi.it/splitmix64.c
// x += 0x9e3779b97f4a7c15;
// x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
// x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
// return x ^ (x >> 31);
// }
// size_t operator()(uint64_t x) const {
// static const uint64_t FIXED_RANDOM = lrng();
// return splitmix64(x + FIXED_RANDOM);
// }
// };
这程序好像有点Bug,我给组数据试试?
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 5728kb
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: 677ms
memory: 37172kb
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