QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#92818 | #4387. Static Query on Tree | zbceyond | WA | 365ms | 72260kb | C++20 | 2.8kb | 2023-03-30 23:58:16 | 2023-03-30 23:58:20 |
Judging History
answer
#include<bits/stdc++.h>
#define rep(i,x,y) for(int i=x;i<=y;i++)
#define per(i,x,y) for(int i=x;i>=y;i--)
using namespace std;
const int N=2e5+10;
const int mod=998244353;
#define int long long
int qmi(int a,int b,int mod){//mod别弄错了
int res=1;
for(;b;b>>=1,a=a*a%mod)
if(b&1)res=res*a%mod;
return res;
}
int dfn[N],dep[N],tot,par[N][22],p[N],colA[N],colB[N],colC[N],ans;
vector<int>e[N];
void dfs(int u,int fa){
dfn[u]=++tot,par[u][0]=fa,dep[u]=dep[fa]+1;
for(auto v:e[u])if(v!=fa){
dfs(v,u);
}
}
int lca(int x,int y){
if(dep[x]>dep[y])swap(x,y);
int tmp=dep[y]-dep[x];
for(int i=20;i>=0;i--){
if(tmp>>i&1)y=par[y][i];
}
if(x==y)return x;
for(int i=20;i>=0;i--){
if(par[x][i]!=par[y][i]) {
x = par[x][i], y =par[y][i];
}
}
return par[x][0];
}
vector<int>E[N];
void dfs1(int u,int fa,int ok){
ok|=colC[u];
for(auto v:E[u])if(v!=fa){
dfs1(v,u,ok);
colA[u]|=colA[v];
colB[u]|=colB[v];
}
//cout<<u<<" "<<colA[u]<<" "<<colB[u]<<" "<<ok<<"\n";
if(colA[u] and colB[u] and ok)ans++;
}
void solve() {
int n, q;
cin >> n >> q;
rep(i, 2, n)cin >> p[i], e[p[i]].push_back(i);
dfs(1,0);
rep(j,1,20)rep(i,1,n)
par[i][j]=par[par[i][j-1]][j-1];
rep(_, 1, q) {
int a, b, c;
cin >> a >> b >> c;
vector<int> A(a), B(b), C(c), vx;
for (auto &i: A)cin >> i, vx.push_back(i),colA[i]=1;
for (auto &i: B)cin >> i, vx.push_back(i),colB[i]=1;
for (auto &i: C)cin >> i, vx.push_back(i),colC[i]=1;
sort(vx.begin(), vx.end(), [&](int &x, int &y) {
return dfn[x] < dfn[y];
});
vector<int> vy;
rep(i, 0, (int) vx.size() - 2) {
vy.push_back(vx[i]);
vy.push_back(lca(vx[i], vx[i + 1]));
}
vy.push_back(vx.back());
sort(vy.begin(), vy.end(), [&](int &x, int &y) {
return dfn[x] < dfn[y];
});
vy.erase(unique(vy.begin(),vy.end()),vy.end());
rep(i,0,(int)vy.size()-2){
int lc=lca(vy[i],vy[i+1]);
E[lc].push_back(vy[i+1]);
E[vy[i+1]].push_back(lc);
//cout<<lc<<" "<<vy[i+1]<<"\n";
}
int rt=vy[0];
dfs1(rt,rt,0);
cout<<ans<<"\n";
for(auto x:vy){
//cout<<x<<"\n";
E[x].clear();
colA[x]=colB[x]=colC[x]=0;
}
ans=0;
}
rep(i,1,n)e[i].clear();
tot=0;
}
signed main() {
cin.tie(nullptr)->sync_with_stdio(false);
int tc = 1;
cin >> tc;
for (int i = 1; i <= tc; i++) {
solve();
}
}
//1
//7 2
//1 1 2 2 3 3
//4 4 3
//4 5 6 7
//4 5 6 7
//2 4 6
//2 1 1
//4 5
//6
//1
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 365ms
memory: 72260kb
input:
1 200000 18309 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 ...
output:
64176 5 6 3 3 7 7 2 8 5 4 7 3 6 6 2 2 2 7 3 4 3 7 3 2 5 6 6 6 6 4 4 3 3 5 5 2 3 3 5 8 2 5 5 6 2 3 4 3 3 5 3 6 6 5 5 4 3 7 2 4 7 5 2 4 4 3 4 4 2 7 5 5 5 4 4 5 3 2 5 8 5 4 2 7 6 2 4 2 3 6 7 5 2 3 7 5 4 2 3 2 5 5 5 5 7 4 4 3 5 5 2 5 2 2 6 2 5 4 8 4 3 4 6 2 6 3 8 3 4 2 3 6 3 5 4 7 4 4 5 6 4 2 3 5 6 3 3 ...
result:
wrong answer 1st numbers differ - expected: '102147', found: '64176'