QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#214628 | #7103. Red Black Tree | Yangmf# | WA | 807ms | 66976kb | C++17 | 3.2kb | 2023-10-14 22:04:20 | 2023-10-14 22:04:20 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int, int> pii;
#define error \
{ \
cout << "No\n"; \
return; \
}
#define all(x) (x.begin(), x.end())
const int N = 1e6 + 10;
int a[N];
int n, m, q;
bool f[N];
vector<pii> ed[N];
pii v[N];
int val[N],fat[N];
void dfs(int x,int fa){
for(auto t:ed[x]){
int y=t.first,z=t.second;
if(y==fa) continue;
if(f[y]) {
val[y]=0;
fat[y]=y;
} else {
val[y]=val[x]+z;
fat[y]=fat[x];
}
dfs(y,x);
}
}
bool cmp(pii x,pii y){
if(x.first!=y.first) return x.first>y.first;
else return x.second>y.second;
}
int d[N],dist[N],fa[N][30];
int ht;
void bfs(){
queue<int> q;
q.push(1);
d[1]=1;
dist[1]=0;
while(q.size()){
int x=q.front(); q.pop();
for(auto t:ed[x]){
int y=t.first,z=t.second;
if(d[y]) continue;
d[y]=d[x]+1;
dist[y]=dist[x]+z;
fa[y][0]=x;
for(int j=1;j<=ht;j++){
fa[y][j]=fa[fa[y][j-1]][j-1];
}
q.push(y);
}
}
}
int lca(int x,int y){
if(d[x]>d[y]) swap(x,y);
for(int i=ht;i>=0;i--){
if(d[fa[y][i]]>=d[x]) y=fa[y][i];
}
if(x==y) return x;
for(int i=ht;i>=0;i--){
if(fa[x][i]!=fa[y][i]) x=fa[x][i],y=fa[y][i];
}
return fa[x][0];
}
const int inf=1e18;
pii me[N];
void solve()
{
cin>>n>>m>>q;
ht=(int)(log(n)/log(2))+1;
for(int i=1;i<=m;i++){
int x;
cin>>x;
f[x]=1;
}
for(int i=1;i<n;i++){
int x,y,z;
cin>>x>>y>>z;
ed[x].push_back({y,z});
ed[y].push_back({x,z});
}
bfs();
val[1]=0;
fat[1]=1;
dfs(1,0);
// for(int i=1;i<=n;i++){
// cout<<val[i]<<" ";
// }
// cout<<"\n";
while(q--){
int k;
cin>>k;
// cout<<"*****\n";
for(int i=1;i<=k;i++) {
int x;
cin>>x;
v[i] = { val[x],fat[x] };
me[i]={val[x],x};
// pt.push_back();
// cout<<x<<" "<<val[x]<<"\n";
}
sort(v+1,v+k+1,cmp);
sort(me+1,me+k+1,cmp);
v[k+1]={-1,0};
int ans;
if(k==1) {
cout<<0<<"\n";
continue;
} else {
ans=v[2].first;
}
int ss=v[1].second;
int pre=me[1].second;
for(int i=2;i<=k;i++){
// cout<<pre<<"\n";
pii t=v[i];
int y=t.first,z=t.second;
if(z!=ss) break;
pre=lca(pre,me[i].second);
ans=min(ans,max(v[i+1].first,v[1].first-(dist[pre]-dist[ss])));
}
cout<<ans<<"\n";
}
for(int i=1;i<=n;i++){
ed[i].clear();
f[i]=0;
}
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t;
cin >> t;
while (t--)
{
solve();
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 3ms
memory: 27160kb
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
Wrong Answer
time: 807ms
memory: 66976kb
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 493591722 493591722 471453091 493591722 1717669833 1717669833 1312647007 1168076167 587526565 285643094 285643094 285643094 317919339 0 916794839 717968006 605409472 479058444 371688030 307718947 566052472 1287389114 910180170 1124931652 121535083 316895493 316895493 316895493 ...
result:
wrong answer 4th lines differ - expected: '319801028', found: '493591722'