QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#662503	#8551. DFS Order 5	HHY_zZhu^#	WA	64ms	3748kb	C++17	2.7kb	2024-10-21 01:50:13	2024-10-21 01:50:14

Judging History

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

[2024-10-21 01:50:14]
评测

测评结果：WA
用时：64ms
内存：3748kb

查看

[2024-10-21 01:50:13]
提交

answer

#include <bits/stdc++.h>
using namespace std;
#define V vector
#define all0(x) (x).begin(),(x).end()
#define all1(x) (x).begin()+1,(x).end()
#define pb push_back
#define fi first
#define se second
#define lb lower_bound
#define ub upper_bound
#define cin std::cin
#define cout std::cout
typedef long long LL;
typedef pair<int, int> pi;
typedef pair<LL, LL> pl;

const int N = 1e5 + 20;
const int INF = 2e9 + 1000;
const LL INFLL = 8e18 + 1000;
mt19937 mrand(chrono::steady_clock().now().time_since_epoch().count());
//模板区域~~~~~~~
struct BIT{
    V<int> old;
    LL fenT[N];//单点修改 + 区间查询 
    void add(int x, LL d) {
        assert(x > 0); 
        while(x < N) {
            fenT[x] += d;
            old.pb(x);
            x += x & (-x);
        } 
    }
    void add(int l, int r, LL d) {
        add(l,d);
        add(r + 1, -d);
    }
    LL query(int x) {
        LL ans = 0;
        while(x >= 1) {
            ans += fenT[x];
            x -= x & -x;
        } 
        return ans;
    }
    LL query(int l, int r) {
        if(r < l) return 0;
        return query(r) - query(l - 1);
    }
    void clear() { 
        for(auto p : old) fenT[p] = 0; 
        old.clear(); 
    }
}fen;
//模板结束~~~~~~~

void solve() {
    int n, q; cin >> n >> q;
    V<V<int>> e(n + 1);
    for(int i = 1; i < n; i++) {
        int a, b; cin >> a >> b;
        e[a].pb(b), e[b].pb(a);
    }
    V<int> l(n + 1), r(n + 1), f(n + 1);
    int tot = 0;
    auto dfs = [&](int x, int p, auto dfs) -> void {
        l[x] = ++tot;
        f[x] = p;
        for(auto y : e[x]) if(y != p) {
            dfs(y, x, dfs);
        }
        r[x] = tot;
    };
    dfs(1, 0, dfs);
    V<int> vis(n + 1);
    for(int i = 1; i <= q; i++) {
        int k; cin >> k;
        fen.clear();
        int now; cin >> now;
        fen.add(l[now], 1);
        vis[now] = i;
        bool ok = 1;
        for(int j = 2; j <= k; j++) {
            int n_now; cin >> n_now;
            if(fen.query(l[n_now], r[n_now])) ok = 0;

            while(vis[now] == i && f[n_now] != now) {
                if(fen.query(l[now], r[now]) != r[now] - l[now] + 1) ok = 0;
                now = f[now];
            }
            now = f[n_now];
            if(now == 0 || fen.query(l[now], r[now]) == 0) {
                ok = 0;
            }
            // cout << "now : " << now << endl; 

            now = n_now;
            vis[now] = i;
            fen.add(l[now], 1);
        }
        cout << (ok ? "Yes" : "No") << endl;
    }
}

int32_t main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t = 1;
    // cin >> t;
    while (t--) 
    solve();
}

Source code, Language: C++17

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100

Accepted

time: 0ms

memory: 3748kb

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: 64ms

memory: 3644kb

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
No
No
No
No
No
No
No
No
No
No
No
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
No
No
No
No
No
No
No
No
N...

result:

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