oj.uz

Submission #914242

# Submission time Handle Problem Language Result Execution time Memory
914242 2024-01-21T12:22:12 Z VMaksimoski008 Regions (IOI09_regions) C++14
100 / 100
 2980 ms 27724 KB 
#include <bits/stdc++.h>
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
 
using namespace std;
using pii = pair<int, int>;
 
const int maxn = 2e5 + 5;
 
int n, r, q, in[maxn], out[maxn], timer = 0, B = 500, curr = 0, dp[210][25005];
short home[maxn], id[maxn];
vector<vector<int> > graph;
vector<vector<pii> > by_home;
 
void dfs(int u) {
    in[u] = timer++;
 
    for(int &v : graph[u])
        dfs(v);
 
    out[u] = timer;
}
 
void dfs2(int u, int R, int cnt) {
    if(home[u] == R) cnt++;
    dp[id[R]][home[u]] += cnt;
    for(int &v : graph[u]) dfs2(v, R, cnt);
}
 
int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    cin >> n >> r >> q;
    graph.resize(n+1);
    by_home.resize(r+1);
    
    cin >> home[1];
 
    for(int i=2; i<=n; i++) {
        int p;
        cin >> p >> home[i];
        graph[p].push_back(i);
    }
 
    dfs(1);
 
    for(int i=1; i<=n; i++)
        by_home[home[i]].push_back({ in[i], out[i] });

    for(int i=1; i<=r; i++) {
        sort(all(by_home[i]));
        if(sz(by_home[i]) <= B) continue;
        id[i] = curr;
        dfs2(1, i, 0);
        curr++;
    }
 
    while(q--) {
        int r1, r2, ans = 0;
        cin >> r1 >> r2;

        if(sz(by_home[r1]) > B) {
            cout << dp[id[r1]][r2] << endl;
            continue;
        }
 
        for(pii &u : by_home[r1]) {
            //cout << u.first << " " << u.second << '\n';
            int l=0, r=sz(by_home[r2])-1;
            int p1 = 1e9;
 
            while(l <= r) {
                int mid = (l + r) / 2;
                if(by_home[r2][mid].first > u.first) p1 = mid, r = mid - 1;
                else l = mid + 1;
            }
 
            if(p1 == 1e9) continue;
            
            l=p1, r=sz(by_home[r2])-1;
            int p2 = 1e9;
 
            while(l <= r) {
                int mid = (l + r) / 2;
                if(by_home[r2][mid].first < u.second) p2 = mid, l = mid + 1;
                else r = mid - 1;
            }
 
            if(p2 == 1e9) continue;
 
            ans += (p2 - p1 + 1);
        }
 
        cout << ans << endl;
    }
    
    return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2388 KB Output is correct
2 Correct 1 ms 2392 KB Output is correct
3 Correct 1 ms 2400 KB Output is correct
4 Correct 2 ms 2392 KB Output is correct
5 Correct 4 ms 2392 KB Output is correct
6 Correct 8 ms 2392 KB Output is correct
7 Correct 14 ms 2392 KB Output is correct
8 Correct 16 ms 2648 KB Output is correct
9 Correct 23 ms 2904 KB Output is correct
10 Correct 36 ms 3160 KB Output is correct
11 Correct 69 ms 3464 KB Output is correct
12 Correct 71 ms 4184 KB Output is correct
13 Correct 94 ms 3928 KB Output is correct
14 Correct 155 ms 4748 KB Output is correct
15 Correct 178 ms 6840 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1215 ms 8664 KB Output is correct
2 Correct 1107 ms 7572 KB Output is correct
3 Correct 1867 ms 10784 KB Output is correct
4 Correct 134 ms 4796 KB Output is correct
5 Correct 194 ms 6096 KB Output is correct
6 Correct 781 ms 6420 KB Output is correct
7 Correct 934 ms 7868 KB Output is correct
8 Correct 784 ms 12328 KB Output is correct
9 Correct 1305 ms 14700 KB Output is correct
10 Correct 2980 ms 18684 KB Output is correct
11 Correct 2379 ms 16044 KB Output is correct
12 Correct 751 ms 17012 KB Output is correct
13 Correct 1008 ms 17204 KB Output is correct
14 Correct 1381 ms 19232 KB Output is correct
15 Correct 1990 ms 21252 KB Output is correct
16 Correct 2111 ms 26784 KB Output is correct
17 Correct 2037 ms 27724 KB Output is correct