/ SeriousOJ /

Record Detail

Time Exceeded


  
# Status Time Cost Memory Cost
#1 Accepted 4ms 5.074 MiB
#2 Accepted 3ms 4.277 MiB
#3 Accepted 161ms 5.953 MiB
#4 Accepted 160ms 4.883 MiB
#5 Accepted 479ms 6.0 MiB
#6 Accepted 1373ms 7.32 MiB
#7 Accepted 1384ms 6.281 MiB
#8 Time Exceeded ≥2100ms ≥24.91 MiB
#9 Time Exceeded ≥2100ms ≥23.934 MiB

Code

#ifndef LOCAL
#include <bits/stdc++.h>
#define debug(...)
#endif

using namespace std;
#define int long long
#define cinv(v) for (auto &it:v) cin>>it;
#define coutv(v) for (auto &it:v) cout<< it<<' '; cout<<'\n';

const int N = 1e5 + 5;
vector<set<int> > t;
vector<int> adj[N];
int n, q, arr[N], tin[N], tout[N], id[N], timer;

void euler_tour(int now, int par) {
    tin[now] = ++timer;
    id[timer] = now;
    for (auto &it: adj[now]) {
        if (it == par) continue;
        euler_tour(it, now);
    }
    tout[now] = timer;
}

set<int> merge(const set<int> &a, const set<int> &b) {
    set<int> ret = a;
    for (auto &it: b) ret.insert(it);
    return ret;
}

set<int> build(int n, int s, int e) {
    if (s == e) {
        return t[n] = {arr[id[s]]};
        debug(n, s, id[s]);
    }
    int m = (s + e) / 2;
    return t[n] = merge(build(n * 2, s, m), build(n * 2 + 1, m + 1, e));
}

set<int> query(int n, int s, int e, int l, int r) {
    if (s > r || e < l) return {};
    if (s >= l && e <= r) return t[n];
    int m = (s + e) / 2;
    return merge(query(n * 2, s, m, l, r), query(n * 2 + 1, m + 1, e, l, r));
}

void shelby() {
    cin >> n;
    timer = 0, t.assign(4 * n, {});
    for (int i = 1; i <= n; ++i) cin >> arr[i], adj[i].clear();
    for (int i = 1; i < n; ++i) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    euler_tour(1, -1);
    build(1, 1, n);
    debug(t);
    int q;
    cin >> q;
    while (q--) {
        int x;
        cin >> x;
        set<int> st = query(1, 1, n, tin[x], tout[x]);
        int sz = tout[x] - tin[x] + 1;
        debug(x, st, sz);
        int ans = sz;
        for (auto &it: st) {
            if (it > sz) break;
            ans--;
        }
        cout << ans << '\n';
    }
}

signed main() {
    cin.tie(0)->sync_with_stdio(0);
    int t = 1;
    cin >> t;
    for (int _ = 1; _ <= t; ++_) {
        // cout << "Case " << _ << ": ";
        shelby();
    }
}

Information

Submit By
Type
Submission
Problem
P1157 Roy and Tree Permutation
Language
C++17 (G++ 13.2.0)
Submit At
2025-01-12 19:28:13
Judged At
2025-01-12 19:28:13
Judged By
Score
35
Total Time
≥2100ms
Peak Memory
≥24.91 MiB