/ SeriousOJ /

Record Detail

Accepted


  
# Status Time Cost Memory Cost
#1 Accepted 15ms 15.27 MiB
#2 Accepted 15ms 15.316 MiB
#3 Accepted 68ms 15.609 MiB
#4 Accepted 83ms 15.52 MiB
#5 Accepted 87ms 15.52 MiB
#6 Accepted 134ms 15.773 MiB
#7 Accepted 105ms 15.805 MiB
#8 Accepted 140ms 18.27 MiB
#9 Accepted 144ms 18.055 MiB
#10 Accepted 147ms 19.066 MiB
#11 Accepted 58ms 26.523 MiB
#12 Accepted 141ms 44.441 MiB
#13 Accepted 136ms 44.441 MiB
#14 Accepted 137ms 44.535 MiB
#15 Accepted 134ms 44.629 MiB
#16 Accepted 138ms 44.488 MiB
#17 Accepted 125ms 44.52 MiB
#18 Accepted 126ms 44.52 MiB
#19 Accepted 124ms 36.02 MiB
#20 Accepted 162ms 35.852 MiB

Code

#include <bits/stdc++.h>
using namespace std;
const int MAX = (int) 1e5+10;

vector<int> graph[MAX],que[MAX];
int a[MAX],tam[MAX],res[MAX];

struct DSU{
    // o que cada grupo carrega de informacao
    struct gp{
        // se precisa adicionar coisa a mais
        int tam;
        set<int> good, bad;

        // inicializar o smol
        void init(int x){
            // se precisa inicializar coisa a mais, passa por parametro
            tam=1;
            if(a[x] == 1) good.insert(1);
            else bad.insert(a[x]);
        }
        void clear(){
            good.clear();
            bad.clear();
        }
        ~gp(){good.clear();bad.clear();}
    };
    
    vector<int> repre;
    vector<gp> smol;
    int n;

    // inicializar passando a qtd de vertices, grupos iniciais
    DSU (int n) : n(n){
        repre.resize(n+10);
        smol.resize(n+10);
        // for(int i=1; i<=n; i++){
        //     repre[i]=i;
        //     smol[i].init(i);
        // }
    }
    ~DSU(){
        repre.clear();
        smol.clear();
    }
    void init(int n){
        this->n = n;
        for(int i=1; i<=n; i++){
            repre[i] = i;
            smol[i].init(i);
        }
    }
    void clear(){
        for(int i=1; i<=n; i++) smol[i].clear();
    }

    // achar o representante do u
    int rep(int u){
        if(u == repre[u]) return u;
        return repre[u]=rep(repre[u]);
    }

    // unir u e v
    void unite(int u,int v,int t){
        u=rep(u);
        v=rep(v);
        if(u == v) return;

        auto &x=smol[u];
        auto &y=smol[v];
        if(y.tam > x.tam){
            unite(v,u,t);
            return;
        }
        
        // da merge nos smols
        merge(x,y,t);
        repre[v]=u;
    }

    // fazer o merge de 2 grupos
    void merge(gp &x, gp &y,int t){
        // faz o merge se precisar
        for(auto w : y.good) x.good.insert(w);
        for(auto w : y.bad) x.bad.insert(w);
        auto it = x.bad.begin();
        while(it != x.bad.end() && *it <= t) {
            x.good.insert(*it);
            it = x.bad.erase(it);
        }
        y.good.clear();
        y.bad.clear();
        x.tam+=y.tam;
    }
};

DSU dsu(MAX);

void set_tam(int u,int ant){
    tam[u] = 1;
    for(auto v: graph[u]){
        if(v == ant) continue;
        set_tam(v,u);
        tam[u] += tam[v];
    }
}

void solve(int u,int ant){
    for(auto v: graph[u]){
        if(v == ant) continue;
        solve(v,u);
        dsu.unite(u,v,tam[u]);
    }
    auto & x = dsu.smol[dsu.rep(u)];
    for(auto v: que[u]) {
        res[v] = tam[u] - int(x.good.size()); 
    }
}

void test(){
    int n;
    cin >> n;
    for(int i=1; i<=n; i++) cin >> a[i];
    dsu.init(n);
    for(int i=1; i<n; i++){
        int x,y;
        cin >> x >> y;
        graph[x].push_back(y);
        graph[y].push_back(x);
    }
    int q;
    cin >> q;
    for(int i=0; i<q; i++){
        int x;
        cin >> x;
        que[x].push_back(i);
    }
    set_tam(1,1);
    solve(1,1);
    for(int i=0; i<q; i++) cout << res[i] << '\n';
    dsu.clear();
    for(int i=1; i<=n; i++) graph[i].clear();
    for(int i=1; i<=n; i++) que[i].clear();
}

int32_t main(){
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int t = 1;
    cin >> t;
    while(t--) test();
    return 0;
}

Information

Submit By
Type
Submission
Problem
P1157 Roy and Tree Permutation
Language
C++17 (G++ 13.2.0)
Submit At
2025-01-03 02:47:32
Judged At
2025-01-03 02:47:32
Judged By
Score
100
Total Time
162ms
Peak Memory
44.629 MiB