Submission #1107577

#	Time	Username	Problem	Language	Result	Execution time	Memory
1107577		FubuGold	Regions (IOI09_regions)	C++14	35 / 100	3000 ms	64312 KiB

regions

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 200000;
const int BLOCK_SZ = 400, MAX_R = 25000;

vector<int> over_sqrt;
int precomp[MAXN / BLOCK_SZ + 2][MAX_R + 1];
int over_sqrt_id[MAX_R + 1];
vector<int> tin_id[MAX_R+1],id[MAX_R+1];
int n,r,q;
vector<int> adj[MAXN+1];
map<int,int> mp[MAXN+1];
int a[MAXN+1];
int tin[MAXN+1],tout[MAXN+1];
int timeDFS = 0;

void dfs_euler(int u) {
    tin[u] = ++timeDFS;
    tin_id[a[u]].push_back(tin[u]);
    id[a[u]].push_back(u);
    for (int i=0;i<adj[u].size();i++) {
        int v = adj[u][i];
        dfs_euler(v);
    }
    tout[u] = timeDFS;
}

void dfs_cal(int u) {
    mp[u][a[u]]++;
    int mx_v = -1;
    for (int i=0;i<adj[u].size();i++) {
        int v = adj[u][i];
        dfs_cal(v);
        if (mx_v == -1 || mp[v].size() > mp[mx_v].size()) mx_v = v;
    }
    if (mx_v == -1) return;
    swap(mp[u],mp[mx_v]);
    for (int i=0;i<adj[u].size();i++) {
        int v = adj[u][i];
        if (v == mx_v) continue;
        for (pair<int,int> x : mp[v]) {
            mp[u][x.first] += x.second;
        }
    }
    int tmp = over_sqrt_id[a[u]];
    if (tmp == -1) return;
    for (pair<int,int> x : mp[u]) {
        if (x.first == a[u]) continue;
        precomp[tmp][x.first] += x.second;
    }
}

int main() {
    cin.tie(0) -> sync_with_stdio(0);
    cin >> n >> r >> q;
    cin >> a[1];
    for (int i=2;i<=n;i++) {
        int x; cin >> x >> a[i];
        adj[x].push_back(i);
    }
    dfs_euler(1);
    memset(over_sqrt_id,-1,sizeof(over_sqrt_id));
    for (int i=1;i<=r;i++) {
        if (tin_id[i].size() > BLOCK_SZ) {
            over_sqrt_id[i] = over_sqrt.size();
            over_sqrt.push_back(i);
        }
    }
    dfs_cal(1);
    while (q--) {
        int r1,r2; cin >> r1 >> r2;
        int tmp = over_sqrt_id[r1];
        if (tmp != -1) cout << precomp[tmp][r2] << endl;
        else {
            int ans = 0;
            for (int i=0;i<id[r1].size();i++) {
                int u = id[r1][i];
//                cerr << u << ' ' << tin[u] << ' ' << tout[u] << '\n';
                int cnt = upper_bound(tin_id[r2].begin(),tin_id[r2].end(),tout[u])
                         -lower_bound(tin_id[r2].begin(),tin_id[r2].end(),tin[u]);
                ans += cnt;
            }
            cout << ans << endl;
        }
    }
    return 0;
}

Compilation message (stderr)

regions.cpp: In function 'void dfs_euler(int)':
regions.cpp:23:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |     for (int i=0;i<adj[u].size();i++) {
      |                  ~^~~~~~~~~~~~~~
regions.cpp: In function 'void dfs_cal(int)':
regions.cpp:33:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |     for (int i=0;i<adj[u].size();i++) {
      |                  ~^~~~~~~~~~~~~~
regions.cpp:40:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |     for (int i=0;i<adj[u].size();i++) {
      |                  ~^~~~~~~~~~~~~~
regions.cpp: In function 'int main()':
regions.cpp:78:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |             for (int i=0;i<id[r1].size();i++) {
      |                          ~^~~~~~~~~~~~~~

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