oj.uz

Submission #1107577

# Submission time Handle Problem Language Result Execution time Memory
1107577 2024-11-01T15:14:06 Z FubuGold Regions (IOI09_regions) C++14
35 / 100
 3000 ms 64312 KB 
#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

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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 18768 KB Output is correct
2 Correct 3 ms 18768 KB Output is correct
3 Correct 5 ms 18768 KB Output is correct
4 Correct 7 ms 18768 KB Output is correct
5 Correct 8 ms 18768 KB Output is correct
6 Correct 19 ms 19024 KB Output is correct
7 Correct 21 ms 19024 KB Output is correct
8 Correct 28 ms 19024 KB Output is correct
9 Correct 30 ms 20048 KB Output is correct
10 Correct 75 ms 19792 KB Output is correct
11 Correct 102 ms 20304 KB Output is correct
12 Correct 126 ms 21328 KB Output is correct
13 Correct 149 ms 21920 KB Output is correct
14 Correct 186 ms 22044 KB Output is correct
15 Correct 219 ms 28240 KB Output is correct

Subtask #2
20.0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 1526 ms 29992 KB Output isn't correct
2 Incorrect 1788 ms 29540 KB Output isn't correct
3 Incorrect 2394 ms 31932 KB Output isn't correct
4 Correct 242 ms 22668 KB Output is correct
5 Correct 303 ms 25936 KB Output is correct
6 Incorrect 515 ms 31604 KB Output isn't correct
7 Incorrect 1159 ms 29512 KB Output isn't correct
8 Incorrect 955 ms 48228 KB Output isn't correct
9 Correct 1894 ms 36968 KB Output is correct
10 Incorrect 2430 ms 58080 KB Output isn't correct
11 Correct 3000 ms 46832 KB Output is correct
12 Incorrect 1151 ms 36992 KB Output isn't correct
13 Incorrect 1663 ms 40684 KB Output isn't correct
14 Incorrect 1938 ms 43108 KB Output isn't correct
15 Incorrect 2751 ms 47664 KB Output isn't correct
16 Incorrect 2728 ms 64312 KB Output isn't correct
17 Incorrect 2672 ms 62880 KB Output isn't correct