Submission #1107581

#	Time	Username	Problem	Language	Result	Execution time	Memory
1107581		FubuGold	Regions (IOI09_regions)	C++14	100 / 100	2954 ms	32840 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];
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,int clr,int cnt) {
    int mx_v = -1;
    if (a[u] != clr) precomp[over_sqrt_id[clr]][a[u]] += cnt;
    for (int i=0;i<adj[u].size();i++) {
        int v = adj[u][i];
        dfs_cal(v,clr,cnt+(a[u] == clr));
    }
}

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,i,0);
        }
    }
    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:22:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |     for (int i=0;i<adj[u].size();i++) {
      |                  ~^~~~~~~~~~~~~~
regions.cpp: In function 'void dfs_cal(int, int, int)':
regions.cpp:32:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |     for (int i=0;i<adj[u].size();i++) {
      |                  ~^~~~~~~~~~~~~~
regions.cpp:30:9: warning: unused variable 'mx_v' [-Wunused-variable]
   30 |     int mx_v = -1;
      |         ^~~~
regions.cpp: In function 'int main()':
regions.cpp:61:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |             for (int i=0;i<id[r1].size();i++) {
      |                          ~^~~~~~~~~~~~~~

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