Submission #1225413

#	Time	Username	Problem	Language	Result	Execution time	Memory
1225413		Bui_Quoc_Cuong	Regions (IOI09_regions)	C++20	0 / 100	58 ms	29512 KiB

regions

#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 5;

int n, r, q;
int e[maxn];
vector <int> g[maxn];

int sz[maxn], heavy[maxn];

vector <array <int, 2>> qry_e[maxn];
int tin[maxn], tout[maxn], arr[maxn], timedfs;
int ans[maxn];

void dfs_sz(int u){
    sz[u] = 1;
    tin[u] = ++ timedfs;
    arr[tin[u]] = u;
    for(int &v : g[u]){
        dfs_sz(v);
        sz[u]+= sz[v];
        if(sz[v] > sz[heavy[u]]) heavy[u] = v;
    }
    tout[u] = timedfs;
}

int count_e[25005];

void add(int u){
    count_e[e[u]]++;
}

void del(int u){
    count_e[e[u]]--;
}

void getAns(int u, bool keeping){
    for(int &v : g[u]) if(v != heavy[u]) getAns(v, 0);
    if(heavy[u]) getAns(heavy[u], 1);

    for(int &v : g[u]) if(v != heavy[u]){
        for(int i = tin[v]; i <= tout[v]; i++) add(arr[i]);
    }
    add(u);

    for(auto [r2, id] : qry_e[e[u]]){
        ans[id]+= count_e[r2];
        ///cout << u << " " << count_e[r2] << "\n";
    }

    if(keeping == 0){
        for(int i = tin[u]; i <= tout[u]; i++) del(arr[i]);
    }
}

void process(void){
    cin >> n >> r >> q;
    for(int i = 1; i <= n; i++){
        if(i == 1) cin >> e[i];
        else{
            int p; cin >> p >> e[i];
            g[p].push_back(i);
        }
    }
    dfs_sz(1);
    for(int i = 1; i <= q; i++){
        int r1, r2; cin >> r1 >> r2;
        qry_e[r1].push_back({r2, i});
    }
    getAns(1, 0);
    for(int i = 1; i <= q; i++){
        cout << ans[i] << '\n';
        fflush(stdout);
    }
}

int main(void){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    #define taskname "kieuoanh"
    if(fopen(taskname".inp", "r")){
        freopen(taskname".inp", "r", stdin); freopen(taskname".out", "w", stdout);
    }
    int tc = 1; /// cin >> tc;
    while(tc--) process();
    return 0;
}

Compilation message (stderr)

regions.cpp: In function 'int main()':
regions.cpp:82:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   82 |         freopen(taskname".inp", "r", stdin); freopen(taskname".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
regions.cpp:82:53: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   82 |         freopen(taskname".inp", "r", stdin); freopen(taskname".out", "w", stdout);
      |                                              ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 15
• Subtask 2: 0 / 85