QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#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();
}

源文件, 语言: C++17

詳細信息

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'