QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#163214 | #7103. Red Black Tree | ucup-team1001 | AC ✓ | 813ms | 26024kb | C++ | 2.6kb | 2023-09-03 22:10:43 | 2023-09-03 22:10:44 |
Judging History
answer
#include<bits/stdc++.h>
#define ll long long
#define LL __int128
#define rep(i,l,r) for(ll i = l; l <= r ? i <= r : i >= r;l <= r ? ++i : --i)
#define irep(i,l,r) for(ll i = l; i <= r; ++i)
#define drep(i,r,l) for(ll i = r; i >= l; --i)
#define abs(x) (x > 0 ? x : -x)
#define ceil(pp,qq) ((pp>0)^(qq>0)?-abs(pp)/abs(qq):pp%qq?pp/qq+1:pp/qq)
#define floor(pp,qq) ((pp>0)^(qq>0)?-ceil(abs(pp),abs(qq)):pp/qq)
using namespace std;
inline ll read(){
ll s=0; bool fl = 0;
char chcc=getchar();
while(chcc<'0'||chcc>'9'){if(chcc == '-')fl = 1;chcc = getchar();}
while(chcc>='0'&&chcc<='9') s=(s<<3)+(s<<1)+(chcc^48),chcc=getchar();
return fl?-s:s;
}
const int N = 100999;
const long long llinf = 100000000000000000;
int ist[N], fa[N][24], S, dpt[N];
ll d[N];
vector<array<int,2>>g[N];
vector<array<int,3>>edge;
void dfs(int x, int dp){
dpt[x] = dp, S = max(S, dpt[x]);
for(auto [v,w] : g[x]){
if(d[v] || v == 1)continue;
fa[v][0] = x, d[v] = d[x] + w;
dfs(v, dp + 1);
}
}
int lca(int u,int v){
if(u == v)return u;
if(dpt[u] < dpt[v])swap(u,v);
for(int i = S; i >= 0; -- i)
if(dpt[fa[u][i]] >= dpt[v])u = fa[u][i];
if(u == v)return u;
for(int i = S; i >= 0; --i){
if(fa[u][i] != fa[v][i])u = fa[u][i], v = fa[v][i];
}
return fa[u][0];
}
void solve(){
int n = read(), m = read(), q = read();
edge.clear();
irep(i,1,n)g[i].clear();
irep(i,1,n)ist[i] = 0, g[i].clear(), d[i] = 0, dpt[i] = 0;
while(m --)ist[read()] = 1;
irep(i,0,n-2){
int u = read(), v = read(), w = read();
edge.push_back({u,v,w});
g[u].push_back({v,w});
g[v].push_back({u,w});
}
dfs(1,0);
irep(i,1,n)g[i].clear();
for(auto [u,v,w] : edge){
if(d[u] > d[v])swap(u,v);
if(ist[v])continue;
if(ist[u])u = 1;
g[u].push_back({v,w});
g[v].push_back({u,w});
}
irep(i,1,n)d[i] = 0, dpt[i] = 0;
fa[1][0] = 1, S = 0;
dfs(1,0);
S = log2(S) + 1;
for(int s = 1; s <= S; ++ s)
for(int i = 1; i <= n; ++i)
fa[i][s] = fa[fa[i][s - 1]][s - 1];
while(q --){
int sk = read(), c = 0;
ll ans = llinf;
vector<int>node;
for(int i = 1; i <= sk; ++i){
int x = read();
if(!ist[x])node.push_back(x);
}
if(node.size() == 0){puts("0");continue;}
sort(node.begin(), node.end(), [](int u,int v){return d[u] > d[v];});
for(int i = 0, x = node[0]; i < node.size(); i ++, x = node[i]){
if(c == 0)c = x;
else c = lca(c, x);
if(i != node.size() - 1)ans = min(ans, max(d[node[0]] - d[c], d[node[i + 1]]));
else ans = min(ans, d[node[0]] - d[c]);
}
printf("%lld\n", ans);
}
}
int main(){
int T = read();
while(T --){
solve();
}
return 0;
}
这程序好像有点Bug,我给组数据试试?
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 7196kb
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: 813ms
memory: 26024kb
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