Submission #780874

#	Time	Username	Problem	Language	Result	Execution time	Memory
780874		minhnhatnoe	Tourism (JOI23_tourism)	C++14	0 / 100	1 ms	320 KiB

tourism

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<vector<int>> g;
namespace centroid{
    int node_active_cnt = 0;
    struct node{
        bool built = false;
        vector<pair<int, int>> par_bid;

        int active_cnt = 0;
        vector<int> branch_cnt;
        void update(int bid, int value){
            node_active_cnt -= active_cnt >= 2;
            active_cnt -= !!branch_cnt[bid];

            branch_cnt[bid] += value;
            
            active_cnt += !!branch_cnt[bid];
            node_active_cnt += active_cnt >= 2;
        }
    };
    vector<node> a;
    vector<int> tsz;
    void dfs_size(int v, int p){
        tsz[v] = 1;
        for (int u: g[v]){
            if (a[u].built || u == p) continue;
            tsz[v] += tsz[u];
        }
    }
    int dfs_find_cen(int v, int p, int rq){
        for (int u: g[v]){
            if (a[u].built || u == p) continue;
            if (tsz[u] >= rq) return dfs_find_cen(u, v, rq);
        }
        return v;
    }
    void dfs_mark_branch(int v, int p, int cen, int b){
        a[v].par_bid.emplace_back(cen, b);
        for (int u: g[v]){
            if (a[u].built || u == p) continue;
            dfs_mark_branch(u, v, cen, b);
        }
    }
    void dfs_centroid(int v){
        dfs_size(v, -1);
        int cen = dfs_find_cen(v, -1, (tsz[v]+1) / 2);
        v = -1;

        a[cen].par_bid.emplace_back(cen, 0);
        a[cen].par_bid.emplace_back(cen, 1);
        a[cen].branch_cnt.emplace_back();
        a[cen].branch_cnt.emplace_back();
        for (int u: g[cen]){
            if (a[u].built) continue;
            dfs_mark_branch(u, cen, cen, a[cen].branch_cnt.size());
            a[cen].branch_cnt.emplace_back();
        }
        a[cen].built = true;
        for (int u: g[cen]){
            if (a[u].built) continue;
            cout << "CEN: " << cen << " " << u << "\n";
            dfs_centroid(u);
        }
    }
    void init(){
        a.resize(g.size());
        tsz.resize(g.size());
        dfs_centroid(0);
    }
    void modify_node(int v, int value){
        for (pair<int, int> par: a[v].par_bid){
            a[par.first].update(par.second, value);
        }
    }
}
vector<int> c;
const int SQRT = 300;
struct query{
    int l, r, idx;
    friend bool operator<(const query &a, const query &b){
        int blocka = a.l / SQRT, blockb = b.l / SQRT;
        if (blocka != blockb) return blocka < blockb;
        if (blocka % 2 == 0) return a.r < b.r;
        else return a.r > b.r;
    }
};
namespace query_state{
    int l=0, r=-1;
    int move_query(int nl, int nr){
        while (r < nr){
            r++;
            centroid::modify_node(c[r], 1);
        }
        while (l > nl){
            l--;
            centroid::modify_node(c[l], 1);
        }
        while (r > nr){
            centroid::modify_node(c[r], -1);
            r--;
        }
        while (l < nl){
            centroid::modify_node(c[l], -1);
            l++;
        }
        return centroid::node_active_cnt;
    }
};
signed main(){
    cin.tie(0)->sync_with_stdio(0);
    int n, m, q; cin >> n >> m >> q;
    g.resize(n);
    for (int i=1; i<n; i++){
        int a, b; cin >> a >> b;
        a--, b--;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    centroid::init();
    c.resize(m);
    for (int i=0; i<m; i++){
        cin >> c[i];
        c[i]--;
    }
    // vector<query> qrs(q);
    // for (int i=0; i<qrs.size(); i++){
    //     cin >> qrs[i].l >> qrs[i].r;
    //     qrs[i].l--, qrs[i].r--;
    //     qrs[i].idx = i;
    // }
    // sort(qrs.begin(), qrs.end());
    // vector<int> result(q);
    // for (const query &cq: qrs){
    //     result[cq.idx] = query_state::move_query(cq.l, cq.r);
    // }
    // for (int i=0; i<result.size(); i++){
    //     cout << result[i] << "\n";
    // }
    for (int i=0; i<q; i++){
        int l, r; cin >> l >> r;
        l--, r--;
        cout << query_state::move_query(l, r) << "\n";
    }
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 5
• Subtask 3: 0 / 7
• Subtask 4: 0 / 18
• Subtask 5: 0 / 24
• Subtask 6: 0 / 41