oj.uz

Submission #1107581

# Submission time Handle Problem Language Result Execution time Memory
1107581 2024-11-01T15:25:46 Z FubuGold Regions (IOI09_regions) C++14
100 / 100
 2954 ms 32840 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];
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

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

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8528 KB Output is correct
2 Correct 2 ms 8528 KB Output is correct
3 Correct 3 ms 8528 KB Output is correct
4 Correct 4 ms 8528 KB Output is correct
5 Correct 7 ms 8528 KB Output is correct
6 Correct 13 ms 8528 KB Output is correct
7 Correct 26 ms 8696 KB Output is correct
8 Correct 23 ms 8784 KB Output is correct
9 Correct 34 ms 9040 KB Output is correct
10 Correct 56 ms 9040 KB Output is correct
11 Correct 99 ms 9296 KB Output is correct
12 Correct 122 ms 9808 KB Output is correct
13 Correct 134 ms 9296 KB Output is correct
14 Correct 182 ms 10064 KB Output is correct
15 Correct 232 ms 12380 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1552 ms 14916 KB Output is correct
2 Correct 1805 ms 13516 KB Output is correct
3 Correct 2391 ms 16868 KB Output is correct
4 Correct 214 ms 9988 KB Output is correct
5 Correct 302 ms 11600 KB Output is correct
6 Correct 553 ms 17408 KB Output is correct
7 Correct 1245 ms 16204 KB Output is correct
8 Correct 961 ms 27960 KB Output is correct
9 Correct 1880 ms 16532 KB Output is correct
10 Correct 2483 ms 32840 KB Output is correct
11 Correct 2954 ms 15792 KB Output is correct
12 Correct 1118 ms 19272 KB Output is correct
13 Correct 1570 ms 19816 KB Output is correct
14 Correct 1878 ms 21400 KB Output is correct
15 Correct 2669 ms 24724 KB Output is correct
16 Correct 2716 ms 31816 KB Output is correct
17 Correct 2546 ms 32328 KB Output is correct