QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#92818#4387. Static Query on TreezbceyondWA 365ms72260kbC++202.8kb2023-03-30 23:58:162023-03-30 23:58:20

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-03-30 23:58:20]
  • 评测
  • 测评结果:WA
  • 用时:365ms
  • 内存:72260kb
  • [2023-03-30 23:58:16]
  • 提交

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'