/ SeriousOJ /

Record Detail

Memory Exceeded


  
# Status Time Cost Memory Cost
#1 Accepted 2ms 3.027 MiB
#2 Memory Exceeded ≥215ms ≥256.016 MiB
#3 Memory Exceeded ≥219ms ≥256.016 MiB

Code

#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>

using namespace std;

const int MAX_N = 100000;
vector<int> tree[MAX_N];
int A[MAX_N];
int in[MAX_N], out[MAX_N], sz[MAX_N];
vector<int> euler_tour;
int timer = 0;

void dfs(int node, int parent) {
    in[node] = timer++;
    euler_tour.push_back(A[node]);
    sz[node] = 1;

    for (int child : tree[node]) {
        if (child != parent) {
            dfs(child, node);
            sz[node] += sz[child];
        }
    }
    out[node] = timer - 1;
}

class FenwickTree {
public:
    FenwickTree(int n) : n(n) {
        tree.resize(n + 1, 0);
    }

    void update(int idx, int val) {
        for (++idx; idx <= n; idx += idx & -idx) {
            tree[idx] += val;
        }
    }

    int query(int idx) {
        int sum = 0;
        for (++idx; idx > 0; idx -= idx & -idx) {
            sum += tree[idx];
        }
        return sum;
    }

    int range_query(int l, int r) {
        return query(r) - query(l - 1);
    }

private:
    int n;
    vector<int> tree;
};

int solve(int x) {
    int S = sz[x];  
    unordered_map<int, int> node_freq;

    for (int i = in[x]; i <= out[x]; ++i) {
        node_freq[euler_tour[i]]++;
    }

    int missing = 0;

    for (int i = 1; i <= S; ++i) {
        if (node_freq[i] == 0) {
            missing++;
        }
    }

    return missing;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int T;
    cin >> T;

    while (T--) {
        int N;
        cin >> N;

        for (int i = 0; i < N; ++i) {
            cin >> A[i];
        }

        for (int i = 0; i < N - 1; ++i) {
            int u, v;
            cin >> u >> v;
            u--; v--;
            tree[u].push_back(v);
            tree[v].push_back(u);
        }

        euler_tour.clear();
        timer = 0;
        dfs(0, -1);

        int Q;
        cin >> Q;

        while (Q--) {
            int x;
            cin >> x;
            x--; 
            cout << solve(x) << "\n";
        }
    }

    return 0;
}

Information

Submit By
Type
Submission
Problem
P1157 Roy and Tree Permutation
Contest
Happy New Year 2025
Language
C++17 (G++ 13.2.0)
Submit At
2025-01-02 16:01:08
Judged At
2025-01-02 16:01:08
Judged By
Score
5
Total Time
≥219ms
Peak Memory
≥256.016 MiB