oj.uz

Submission #999475

# Submission time Handle Problem Language Result Execution time Memory
999475 2024-06-15T14:37:09 Z fryingduc Regions (IOI09_regions) C++17
55 / 100
 2964 ms 48708 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] = 0;
        dfs_build(1, i);
        for(int j = 1; j <= r; ++j) {
            if(u == j) continue;
            for(auto vertex:regions[j]) {
                calc[id[i]][j] += depth[vertex];
                calc_child[id[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 4 ms 17240 KB Output is correct
3 Correct 5 ms 17240 KB Output is correct
4 Correct 5 ms 17240 KB Output is correct
5 Correct 7 ms 17496 KB Output is correct
6 Correct 9 ms 17496 KB Output is correct
7 Correct 16 ms 17336 KB Output is correct
8 Correct 23 ms 17544 KB Output is correct
9 Correct 33 ms 18008 KB Output is correct
10 Correct 50 ms 18008 KB Output is correct
11 Correct 86 ms 18520 KB Output is correct
12 Correct 108 ms 19032 KB Output is correct
13 Correct 125 ms 20824 KB Output is correct
14 Correct 177 ms 21660 KB Output is correct
15 Correct 276 ms 24244 KB Output is correct

Subtask #2
40.0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 851 ms 27356 KB Output isn't correct
2 Incorrect 840 ms 25592 KB Output isn't correct
3 Incorrect 1634 ms 29816 KB Output isn't correct
4 Correct 173 ms 21592 KB Output is correct
5 Correct 261 ms 23128 KB Output is correct
6 Correct 816 ms 22608 KB Output is correct
7 Correct 1020 ms 24152 KB Output is correct
8 Correct 934 ms 29104 KB Output is correct
9 Correct 1485 ms 30540 KB Output is correct
10 Correct 2964 ms 34852 KB Output is correct
11 Correct 2725 ms 30276 KB Output is correct
12 Incorrect 929 ms 33676 KB Output isn't correct
13 Incorrect 1273 ms 34380 KB Output isn't correct
14 Incorrect 1544 ms 33976 KB Output isn't correct
15 Incorrect 2329 ms 40028 KB Output isn't correct
16 Incorrect 2566 ms 48708 KB Output isn't correct
17 Incorrect 2288 ms 47424 KB Output isn't correct