QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#416639#8720. BFS 序 0Afterlife#WA 112ms740392kbC++173.6kb2024-05-22 01:18:062024-05-22 01:18:07

Judging History

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

  • [2024-05-22 01:18:07]
  • 评测
  • 测评结果:WA
  • 用时:112ms
  • 内存:740392kb
  • [2024-05-22 01:18:06]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;

const int N=1e6+1e3+7;

int n,st[N],ed[N],dep[N],dc;

vector<int> g[N];

int anc[N][21];

void dfs(int x,int f)
{
    st[x]=++dc;
    anc[x][0]=f;
    for(int j=1;j<=20;j++)
        anc[x][j]=anc[anc[x][j-1]][j-1];
    for(auto v:g[x])
    {
        if(v==f)
            continue;
        dep[v]=dep[x]+1;
        dfs(v,x);
    }
    ed[x]=dc;
}

int fup(int a,int b)
{
    for(int i=20;i>=0;i--)
        if(dep[a]-(1<<i)>dep[b])
            a=anc[a][i];
    return a;
}

int lca(int x,int y)
{
    if(dep[x]<dep[y])
        swap(x,y);
    for(int i=20;i>=0;i--)
        if(dep[x]-(1<<i)>=dep[y])
            x=anc[x][i];
    if(x==y)
        return x;
    for(int i=20;i>=0;i--)
        if(anc[x][i]!=anc[y][i])
            x=anc[x][i],y=anc[y][i];
    return anc[x][0];
}

namespace SOLVE {
  int m, i, a[N], q[N], t, tot;
  int pos[N];

  void dfs(int x)
  {
    for(auto v:g[x])
        dfs(v),pos[x]=min(pos[x],pos[v]);
  }
  bool vip[N], vis[N];
  bool cmp(int x, int y) { return st[x] < st[y]; }
  vector<int> g[N];
  queue<int> Q[N];
  void solve(vector<int> v,vector<int> seq) {
	for(int i=0;i+1<seq.size();i++)
    {
        int x=seq[i],y=seq[i+1];
        if(dep[x]!=dep[y])
            continue;
        int z=lca(x,y);
        v.push_back(fup(x,z));
        v.push_back(fup(y,z));
    }
    sort(v.begin(),v.end());
    v.erase(unique(v.begin(),v.end()),v.end());
    int la=-1;
    bool ok=1;
    for(auto x:seq)
    {
        if(dep[x]<la)
            ok=0;
        la=dep[x];
    }
    if(!ok)
    {
        cout<<"No\n";
        return;
    }
    if (!v.size())
      return;
    vis[1] = vip[1] = a[1] = 1;
    m = v.size();
    for (tot = ++m, i = 2; i <= m; i++)
      a[i] = v.back(), v.pop_back(), vis[a[i]] = vip[a[i]] = 1;
    sort(a + 1, a + m + 1, cmp);
    int x;
    for (i = 1; i < m; i++)
      if (!vis[x = lca(a[i], a[i + 1])])
        vis[a[++tot] = x] = 1;
    vector<int> use;
    m = tot, sort(a + 1, a + m + 1, cmp);
    for (q[t = 1] = 1, i = 2; i <= m; q[++t] = a[i++]) {
      while (st[a[i]] < st[q[t]] || ed[a[i]] > ed[q[t]]) // dfs order
        t--;
      if (q[t] != a[i])
        g[q[t]].push_back(a[i]);
      use.push_back(q[t]);
      use.push_back(a[i]);
    }
    for(auto x:use)
        pos[x]=1e9;
    // solve the problem
    for(int i=0;i<seq.size();i++)
        pos[seq[i]]=i;
    dfs(1);
    set<int> s;
    Q[0].push(1);
    s.insert(0);
    auto it=seq.begin();
    while(!s.empty())
    {
        int d=*s.begin();
        while(!Q[d].empty())
        {
            int x=Q[d].front();
            Q[d].pop();
            if(it!=seq.end()&&x==*it)
                it++;
            sort(g[x].begin(),g[x].end(),[&](const int &a,const int &b){return pos[a]<pos[b];});
            for(auto v:g[x])
            {
                Q[dep[v]].push(v);
                s.insert(dep[v]);
            }
        }
        s.erase(s.begin());
    }
    ok&=it==seq.end();
    if(ok)
        cout<<"Yes\n";
    else
        cout<<"No\n";
    for (auto x : use)
      vis[x] = vip[x] = 0, g[x].clear();
    return;
  }
} // namespace SOLVE

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n;
    for(int i=2;i<=n;i++)
    {
        int f;
        cin>>f;
        g[f].push_back(i);
    }
    dfs(1,0);
    int m;
    cin>>m;
    while(m--)
    {
        int k;
        cin>>k;
        vector<int> s;
        while(k--)
        {
            int x;
            cin>>x;
            s.push_back(x);
        }
        SOLVE::solve(s,s);
    }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 112ms
memory: 740392kb

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
No
No
No
No
No
No
No
Yes

result:

wrong answer expected YES, found NO [3rd token]