oj.uz

Submission #914243

# Submission time Handle Problem Language Result Execution time Memory
914243 2024-01-21T12:24:22 Z VMaksimoski008 Regions (IOI09_regions) C++14
100 / 100
 2337 ms 30388 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 = 320, curr = 0, dp[320][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 2392 KB Output is correct
2 Correct 1 ms 2392 KB Output is correct
3 Correct 1 ms 2392 KB Output is correct
4 Correct 2 ms 2392 KB Output is correct
5 Correct 4 ms 2392 KB Output is correct
6 Correct 7 ms 2392 KB Output is correct
7 Correct 13 ms 2392 KB Output is correct
8 Correct 15 ms 2648 KB Output is correct
9 Correct 28 ms 2904 KB Output is correct
10 Correct 38 ms 3160 KB Output is correct
11 Correct 63 ms 3452 KB Output is correct
12 Correct 76 ms 4184 KB Output is correct
13 Correct 93 ms 3928 KB Output is correct
14 Correct 155 ms 4752 KB Output is correct
15 Correct 170 ms 6848 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1140 ms 10720 KB Output is correct
2 Correct 1156 ms 7576 KB Output is correct
3 Correct 1984 ms 10776 KB Output is correct
4 Correct 206 ms 4800 KB Output is correct
5 Correct 220 ms 6096 KB Output is correct
6 Correct 345 ms 12680 KB Output is correct
7 Correct 777 ms 12080 KB Output is correct
8 Correct 667 ms 23672 KB Output is correct
9 Correct 1309 ms 14820 KB Output is correct
10 Correct 1957 ms 30388 KB Output is correct
11 Correct 2337 ms 15704 KB Output is correct
12 Correct 757 ms 17012 KB Output is correct
13 Correct 1113 ms 17204 KB Output is correct
14 Correct 1478 ms 19228 KB Output is correct
15 Correct 1950 ms 21256 KB Output is correct
16 Correct 2066 ms 26624 KB Output is correct
17 Correct 2081 ms 27716 KB Output is correct