QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#808324#8551. DFS Order 5ucup-team2179WA 0ms9940kbC++232.8kb2024-12-10 19:50:102024-12-10 19:50:14

Judging History

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

  • [2024-12-10 19:50:14]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:9940kb
  • [2024-12-10 19:50:10]
  • 提交

answer

#include<bits/stdc++.h>
#define int long long
#define pb push_back
#define pii pair<int, int>
using namespace std;
const int maxn=300050;
int par[maxn][22];
int dep[maxn];
int siz[maxn];
int C=20;
int L[maxn];
int R[maxn];
int cnt=0;
vector<int>  a[maxn];
void dfs(int u,int pre)  //根节点深度为1
{
    dep[u]=dep[pre]+1;
    cnt++;
    L[u]=cnt;
    par[u][0]=pre;
    siz[u]=1;
    for(int i=1;i<C;i++)
    {
        par[u][i]=par[par[u][i-1]][i-1];
    }
    for(auto p:a[u])
    {
        if(p==pre)
            continue;
        dfs(p,u);
        siz[u]+=siz[p];
    }
    R[u]=cnt;
}
int lca(int x,int y)
{
    if(dep[y]>dep[x])swap(x,y);
    
    for(int i=C-1;i>=0;i--)
    {
        if(dep[par[x][i]]>=dep[y])
        x=par[x][i];
    }
    if(x==y)return y;
    for(int i=C-1;i>=0;i--)
    if(par[x][i]!=par[y][i])
    {
        x=par[x][i];
        y=par[y][i];
    }
    return par[x][0];
}
int LCA(int u, int v) {
    return lca(u, v);
}
struct stable {
    vector<vector<int>> mylist;
    int n;
    int (*op) (int a, int b);
    stable(vector<int>&a, int(*f)(int, int)) {
        op = f;
        n = a.size() - 1;
        mylist = vector<vector<int>> (n + 1, vector<int>(__lg(n) + 1));
        for (int i = 1; i <= n; i++) mylist[i][0] = a[i];
        for (int j = 1; j <= __lg(n); j++)
            for (int i = 1; i <= n - (1 << j) + 1; i++)
                mylist[i][j] = op(mylist[i][j - 1], mylist[i + (1 << j - 1)][j - 1]);
    }
    int q(int l, int r) {
        assert(l >= 1 && r <= n && l <= r);
        int len = __lg(r - l + 1);
        return op(mylist[l][len], mylist[r - (1 << len) + 1][len]);
    }
};
void solve() {
    int n, q; cin >> n >> q;
    for (int i = 1; i < n; i++) {
        int u, v; cin >> u >> v;
        a[u].push_back(v);
        a[v].push_back(u);
    }
    dfs(1, 0);
    while (q--) {
        int k; cin >> k;
        set<int> s;
        vector<int> arr(k + 1);
        for (int i = 1; i <= k; i++) cin >> arr[i], s.insert(arr[i]);
        if (s.size() != k) {
            cout << "No\n";
            continue;
        }
        s.clear();
        stable st(arr, LCA);
        int flag = 1;
        // for (int i = 1; i < k && flag; i++)
        //     flag &= (LCA(arr[i], arr[i + 1]) == par[arr[i + 1]][0]);
        for (int i = 1; i <= k && flag; i++) {
            flag &= (arr[i] == st.q(i, min(k, i + siz[arr[i]] - 1)));
        }
        for (int i = 1; i <= k && flag; i++) {
            if(s.lower_bound(L[arr[i]])!=s.end()&&*s.lower_bound(L[arr[i]])<=R[arr[i]])flag=0;
            s.insert(L[arr[i]]);
        }
        if (flag) cout << "Yes\n";
        else cout << "No\n";
    }
}
signed main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t = 1;
    // cin >> t;
    while (t--) solve();
    return 0;
}

详细

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 9940kb

input:

6 7
1 2
1 3
2 4
3 5
2 6
2 4 1
2 4 2
2 4 3
2 4 4
2 4 5
2 4 6
6 1 2 6 4 3 5

output:

No
No
Yes
No
Yes
Yes
Yes

result:

wrong answer 5th words differ - expected: 'No', found: 'Yes'