oj.uz

Submission #999481

# Submission time Handle Problem Language Result Execution time Memory
999481 2024-06-15T14:58:41 Z fryingduc Regions (IOI09_regions) C++17
100 / 100
 2903 ms 50308 KB 
#include "bits/stdc++.h"
using namespace std;

const int maxn = 2e5 + 5;
const int maxr = 25005;
const int B = 500;
int n, r, q;
int h[maxn];
vector<int> heavy;
vector<int> regions[maxn];
vector<pair<int, int>> t[maxn];
vector<int> g[maxn];
int timer, tin[maxn], tout[maxn];
int calc[B + 5][maxr];
int calc_child[B + 5][maxr];
int id[maxr], depth[maxn];
int sz[maxn];
int et[maxn * 2];

void dfs(int u) {
    tin[u] = ++timer;
    et[timer] = u;
    for(auto v:g[u]) {
        dfs(v);
    }
    tout[u] = ++timer;
    et[timer] = u;
}
void dfs_build(int u, int color) {
    if(h[u] == color) ++depth[u];
    sz[u] = (h[u] == color);
    for(auto v:g[u]) {
        depth[v] = depth[u];
        dfs_build(v, color);
        sz[u] += sz[v];
    }
}
void solve() {
    cin >> n >> r >> q;
    cin >> h[1];
    for(int i = 2; i <= n; ++i) {
        int p; cin >> p >> h[i];
        g[p].push_back(i);
    }    
    dfs(1);
    for(int i = 1; i <= n; ++i) {
        regions[h[i]].push_back(i);
    }
    heavy.push_back(0);
    for(int i = 1; i <= r; ++i) {
        if((int)regions[i].size() > B) {
            id[i] = (int)heavy.size();
            heavy.push_back(i);
        }   
        for(auto u:regions[i]) {
            t[i].push_back({tin[u], 1});
            t[i].push_back({tout[u], -1});
        }
        sort(t[i].begin(), t[i].end());
    }
    for(int i = 1; i < (int)heavy.size(); ++i) {
        int u = heavy[i];
        for(int j = 1; j <= n; ++j) depth[j] = sz[j] = 0;
        dfs_build(1, u);
        for(int j = 1; j <= r; ++j) {
            if(u == j) continue;
            for(auto vertex:regions[j]) {
                calc[i][j] += depth[vertex];
                calc_child[i][j] += sz[vertex];
            }
        }
    }
    vector<pair<int ,int>> cur;
    while(q--) {
        int x, y; cin >> x >> y;
        if(id[x]) {
            cout << calc[id[x]][y] << endl;
        }
        else {
            if(id[y]) {
                cout << calc_child[id[y]][x] << endl;
            }
            else {
                cur.resize((int)t[x].size() + (int)t[y].size());
                merge(t[x].begin(), t[x].end(),
                t[y].begin(), t[y].end(), cur.begin());
                
                int res = 0, sum = 0;
                for(auto i:cur) {
                    if(h[et[i.first]] == y) {
                        if(i.second == 1) res += sum;
                    }
                    else {
                        sum += i.second;
                    }
                }
                cout << res << endl;
            }
        }
    }
    
}
signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    solve();
    return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 17240 KB Output is correct
2 Correct 3 ms 17240 KB Output is correct
3 Correct 5 ms 17240 KB Output is correct
4 Correct 7 ms 17240 KB Output is correct
5 Correct 7 ms 17496 KB Output is correct
6 Correct 12 ms 17496 KB Output is correct
7 Correct 17 ms 17496 KB Output is correct
8 Correct 15 ms 17496 KB Output is correct
9 Correct 34 ms 18008 KB Output is correct
10 Correct 49 ms 18008 KB Output is correct
11 Correct 97 ms 18520 KB Output is correct
12 Correct 97 ms 19032 KB Output is correct
13 Correct 131 ms 20824 KB Output is correct
14 Correct 175 ms 21592 KB Output is correct
15 Correct 290 ms 24248 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 916 ms 27416 KB Output is correct
2 Correct 908 ms 25820 KB Output is correct
3 Correct 1775 ms 29852 KB Output is correct
4 Correct 198 ms 21592 KB Output is correct
5 Correct 252 ms 23128 KB Output is correct
6 Correct 820 ms 22616 KB Output is correct
7 Correct 1048 ms 24152 KB Output is correct
8 Correct 923 ms 29008 KB Output is correct
9 Correct 1557 ms 30544 KB Output is correct
10 Correct 2903 ms 34644 KB Output is correct
11 Correct 2692 ms 30280 KB Output is correct
12 Correct 893 ms 33744 KB Output is correct
13 Correct 1238 ms 34440 KB Output is correct
14 Correct 1499 ms 36684 KB Output is correct
15 Correct 2297 ms 40120 KB Output is correct
16 Correct 2567 ms 48836 KB Output is correct
17 Correct 2252 ms 50308 KB Output is correct