QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#417929	#8720. BFS 序 0	OOBMABTRAMS^#	WA	326ms	59044kb	C++23	2.1kb	2024-05-23 02:42:07	2024-05-23 02:42:09

Judging History

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

[2024-05-23 02:42:09]
评测

测评结果：WA
用时：326ms
内存：59044kb

查看

[2024-05-23 02:42:07]
提交

answer

#include<bits/stdc++.h>
using namespace std;
const int N=300013;
vector<int>mp[N];
int dfn[N],dep[N],mnd[19][N],tot;
int s[N],t;
vector<pair<int,int>>mp_[N];
void dfs(int x,int fa){
    dep[x]=dep[fa]+1,mnd[0][dfn[x]=++tot]=fa;
    for(auto i:mp[x])if(i^fa)dfs(i,x);
}
int get(int x,int y){return dep[x]<dep[y]?x:y;}
int lca(int x,int y){
    if(x==y)return x;
    x=dfn[x],y=dfn[y];
    if(x>y)swap(x,y);
    int i=__lg(y-x++);
    return get(mnd[i][x],mnd[i][y-(1<<i)+1]);
}
void get_lca(int n){
    tot=0,dfs(1,0);
    for(int i=1;i<=18;i++)for(int j=1;j+(1<<i)-1<=n;j++)
            mnd[i][j]=get(mnd[i-1][j],mnd[i-1][j+(1<<(i-1))]);
}
int id[N];

int vis[N],dis[N];
void wk(){
    int x,sz;
    cin>>x;
    vector<int>v(x),v1,v2;
    int k=0;
    for(auto&p:v)cin>>p,id[p]=++k;
    v1=v;
    sort(v.begin(),v.end(),[&](int x,int y){return dfn[x]<dfn[y];});
    for(int i=1;i<x;i++)v.push_back(lca(v[i],v[i-1]));
    sort(v.begin(),v.end(),[&](int x,int y){return dfn[x]<dfn[y];});
    v.resize(unique(v.begin(),v.end())-v.begin());
    sz=v.size();
    s[t=1]=v[0];
    for(int i=1;i<sz;i++){
        while(t){
            if(lca(s[t],v[i])==s[t]){
                mp_[s[t]].emplace_back(dep[v[i]]-dep[s[t]],v[i]);
                break;
            }
            t--;
        }
        s[++t]=v[i];
    }
    priority_queue<tuple<int,int,int>>pq;
    for(auto x:v)vis[x]=0,dis[x]=1e9;
    dis[v[0]]=0;
    pq.push({0,-id[v[0]],v[0]});
    while(!pq.empty()){
        auto[len,I,x]=pq.top();
        pq.pop();
        if(vis[x])continue;
        vis[x]=1;
        if(id[x])v2.push_back(x);
        for(auto[l,i]:mp_[x])if(l+dis[x]<dis[i])dis[i]=l+dis[x],pq.push({-dis[i],-id[i],i});
    }
    int flg=1;
    for(int i=0;i<v1.size();i++)flg&=v1[i]==v2[i];
    for(auto&p:v)mp_[p].resize(0),id[p]=0;

    cout<<(flg?"Yes":"No")<<'\n';
}
int main()
{
    int n;cin>>n;
    for(int i=2;i<=n;i++)
    {
        int x;cin>>x;
        mp[x].push_back(i);
        mp[i].push_back(x);
    }
    get_lca(n);
    //dfs(1,0);
    int q;
    cin>>q;
    for(int i=1;i<=q;i++) wk();
}

源文件, 语言: C++23

詳細信息

Test #1:

score: 100

Accepted

time: 0ms

memory: 9960kb

input:

6
1 1 3 2 4
10
4 3 6 2 5
1 4
3 2 4 5
5 2 5 4 6 3
3 1 4 2
3 5 6 3
5 4 5 2 6 1
4 4 3 2 5
4 4 6 2 3
3 3 2 6

output:

No
Yes
Yes
No
No
No
No
No
No
Yes

result:

ok 10 token(s): yes count is 3, no count is 7

Test #2:

score: -100

Wrong Answer

time: 326ms

memory: 59044kb

input:

300000
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1...

output:

No
Yes
Yes
Yes
No
No
No
No
No
No
Yes
Yes
No
Yes
No
Yes
Yes
Yes
No
No
No
No
Yes
No
No
Yes
No
No
No
No
Yes
Yes
Yes
No
No
Yes
No
No
No
No
No
No
No
Yes
No
Yes
No
Yes
No
No
No
No
Yes
Yes
Yes
No
No
Yes
No
No
No
No
No
Yes
Yes
No
No
No
No
No
Yes
Yes
No
Yes
No
No
No
Yes
No
No
Yes
No
No
Yes
Yes
Yes
Yes
No
No
...

result:

wrong answer expected NO, found YES [87th token]