QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#808248#8551. DFS Order 5ucup-team2179WA 54ms9748kbC++232.8kb2024-12-10 18:52:402024-12-10 18:52:40

Judging History

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

  • [2024-12-10 18:52:40]
  • 评测
  • 测评结果:WA
  • 用时:54ms
  • 内存:9748kb
  • [2024-12-10 18:52:40]
  • 提交

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]++;
    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;
        siz[u]+=siz[p];
        dfs(p,u);
    }
    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[i])!=s.end()&&*s.lower_bound(L[i])<=R[i])flag=0;
            s.insert(L[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;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 9676kb

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

result:

ok 7 tokens

Test #2:

score: -100
Wrong Answer
time: 54ms
memory: 9748kb

input:

10 100000
7 2
1 7
7 10
8 6
8 7
1 3
4 5
9 5
5 8
8 8 9 7 2 8 1 6 1
4 8 3 5 2
6 7 10 3 9 9 1
1 1
8 10 3 2 9 3 8 7 3
7 5 6 2 8 5 9 1
6 3 4 6 2 1 3
5 8 9 2 4 9
1 3
2 1 5
5 8 5 1 7 9
10 5 2 9 2 6 4 10 6 3 8
3 4 5 8
2 8 4
9 4 10 1 2 4 3 3 6 3
1 3
6 1 1 6 8 3 1
3 7 3 2
3 9 1 5
4 3 7 8 10
9 4 2 3 10 2 5 4 3 ...

output:

No
No
No
Yes
No
No
No
No
Yes
No
No
No
No
No
No
Yes
No
No
No
Yes
No
No
No
No
No
No
No
No
No
Yes
No
Yes
No
No
No
No
No
No
Yes
No
No
No
No
No
Yes
Yes
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
Yes
No
No
Yes
Yes
No
No
No
No
Yes
No
No
No
No
No
No
No
No
Yes
No
No
No
No
No
No
N...

result:

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