QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#159672 | #7103. Red Black Tree | ucup-team191# | AC ✓ | 1065ms | 29296kb | C++17 | 2.7kb | 2023-09-02 18:18:15 | 2023-09-02 18:18:15 |
Judging History
answer
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <iostream>
#include <map>
#include <set>
#include <vector>
#define X first
#define Y second
#define PB push_back
using namespace std;
typedef long long ll;
typedef pair < int, int > pii;
typedef vector < int > vi;
typedef pair < ll, int > pli;
const int N = 1e5 + 500;
const int M = 1e6 + 500;
const int LOG = 18;
const int OFF = (1 << 20);
const int INF = 0x3f3f3f3f;
const ll LINF = (ll)1e18;
const int MOD = 1e9 + 7; // 998244353
inline int add(int A, int B) {
if(A + B >= MOD)
return A + B - MOD;
return A + B;
}
inline int sub(int A, int B) {
if(A - B < 0)
return A - B + MOD;
return A - B;
}
inline int mul(int A, int B) {
return (ll)A * B % MOD;
}
inline int pot(int A, int B) {
int ret = 1, bs = A;
for(;B;B >>= 1) {
if(B & 1) ret = mul(ret, bs);
bs = mul(bs, bs);
}
return bs;
}
int n, m, q, dep[M];
ll dis[N], rd[N];
vector < pli > v[N];
int par[N][LOG];
void dfs(int x, int lst, ll zad){
if(rd[x] == -1) rd[x] = dis[x] - zad;
else zad = dis[x];
par[x][0] = lst;
for(auto nxt : v[x]) {
if(nxt.Y == lst) continue;
dep[nxt.Y] = dep[x] + 1;
dis[nxt.Y] = dis[x] + nxt.X;
dfs(nxt.Y, x, zad);
}
}
void prepare_lca(){
for(int j = 1;j < LOG;j++) {
for(int i = 1;i <= n;i++) {
par[i][j] = par[par[i][j - 1]][j - 1];
}
}
}
inline int get_lca(int x, int y) {
if(dep[x] < dep[y]) swap(x, y);
for(int i = 17;i >= 0;i--)
if(dep[x] - (1 << i) >= dep[y]) x = par[x][i];
if(x == y) return x;
for(int i = 17;i >= 0;i--)
if(par[x][i] != par[y][i]) x = par[x][i], y = par[y][i];
return par[x][0];
}
bool cmp(int x, int y) {
return rd[x] > rd[y];
}
void solve(){
scanf("%d%d%d", &n, &m, &q);
for(int i = 1;i <= n;i++) rd[i] = -1;
for(;m--;) {
int x; scanf("%d", &x); rd[x] = 0;
}
for(int i = 1;i < n;i++) {
int a, b, c; scanf("%d%d%d", &a, &b, &c);
v[a].PB({c, b}); v[b].PB({c, a});
}
dfs(1, 1, 0); prepare_lca();
for(;q--;) {
int ln; scanf("%d", &ln);
vector < int > v;
ll ans = 0;
for(;ln--;) {
int x; scanf("%d", &x); v.PB(x);
ans = max(ans, rd[x]);
}
sort(v.begin(), v.end(), cmp);
int lc = v[0];
ll najdub = dis[v[0]];
for(int i = 0;i < (int)v.size();i++) {
lc = get_lca(v[i], lc);
najdub = max(najdub, dis[v[i]]);
ans = min(ans, max(i + 1 < (int)v.size() ? rd[v[i + 1]] : 0,
najdub - dis[lc]));
}
printf("%lld\n", ans);
}
for(int i = 1;i <= n;i++) v[i].clear();
}
int main(){
//ios_base::sync_with_stdio(false);
//cin.tie(0);
//int T = 1;
int T; scanf("%d", &T);
for(;T--;) solve();
return 0;
}
这程序好像有点Bug,我给组数据试试?
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 9928kb
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: 1065ms
memory: 29296kb
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