oj.uz

Submission #1071887

# Submission time Handle Problem Language Result Execution time Memory
1071887 2024-08-23T12:08:39 Z ArthuroWich Regions (IOI09_regions) C++17
80 / 100
 8000 ms 32732 KB 
#include <bits/stdc++.h>
using namespace std;
vector<int> adj[300005], reg[25005], regst[25005], calc[25005];
int st[300005], en[300005], timer = 0;
void dfs(int i, int p) {
    st[i] = timer;
    timer++;
    for (int j : adj[i]) {
        if (j == p) {
            continue;
        }
        dfs(j, i);
    }
    en[i] = timer;
}
void solve() {
    int n, r, q;
    cin >> n >> r >> q;
    for (int i = 1; i <= n; i++) {
        int s, h;
        if (i == 1) {
            cin >> h;
            reg[h].push_back(i);
        } else {
            cin >> s >> h;
            reg[h].push_back(i);
            adj[s].push_back(i);
            adj[i].push_back(s);
        }
    }
    dfs(1, -1);
    for (int i = 1; i <= r; i++) {
        for (int j : reg[i]) {
            regst[i].push_back(st[j]);
        }
        sort(regst[i].begin(), regst[i].end());
    }
    int block = 400;
    for (int a = 1; a <= r; a++) {
        if (reg[a].size() > 400) {
            calc[a].resize(r+1, 0);
            for (int b = 1; b <= r; b++) {
                if (a == b) {
                    continue;   
                }
                for (int i : reg[a]) {
                    int l, r;
                    l = upper_bound(regst[b].begin(), regst[b].end(), st[i]) - regst[b].begin();
                    r = lower_bound(regst[b].begin(), regst[b].end(), en[i]) - regst[b].begin();
                    calc[a][b] += r-l;
                }
            }
        }
    }
    while(q--) {
        int a, b, ans = 0;
        cin >> a >> b;
        if (reg[a].size() <= 400) {
            for (int i : reg[a]) {
                int l, r;
                l = upper_bound(regst[b].begin(), regst[b].end(), st[i]) - regst[b].begin();
                r = lower_bound(regst[b].begin(), regst[b].end(), en[i]) - regst[b].begin();
                ans += r-l;
            }
        } else {
            ans += calc[a][b];
        }
        cout << ans << endl;
    }
}
int32_t main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t;
    t = 1;
    while(t--) {
        solve();
    }
}

Compilation message

regions.cpp: In function 'void solve()':
regions.cpp:38:9: warning: unused variable 'block' [-Wunused-variable]
   38 |     int block = 400;
      |         ^~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 9304 KB Output is correct
2 Correct 3 ms 9304 KB Output is correct
3 Correct 4 ms 9304 KB Output is correct
4 Correct 5 ms 9304 KB Output is correct
5 Correct 8 ms 9304 KB Output is correct
6 Correct 13 ms 9304 KB Output is correct
7 Correct 17 ms 9304 KB Output is correct
8 Correct 20 ms 9304 KB Output is correct
9 Correct 22 ms 9816 KB Output is correct
10 Correct 61 ms 9816 KB Output is correct
11 Correct 86 ms 10072 KB Output is correct
12 Correct 104 ms 10584 KB Output is correct
13 Correct 133 ms 10584 KB Output is correct
14 Correct 226 ms 10840 KB Output is correct
15 Correct 195 ms 13144 KB Output is correct

Subtask #2
65.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1752 ms 13796 KB Output is correct
2 Correct 2050 ms 13644 KB Output is correct
3 Correct 2640 ms 15192 KB Output is correct
4 Correct 201 ms 11096 KB Output is correct
5 Correct 248 ms 12376 KB Output is correct
6 Correct 2588 ms 14032 KB Output is correct
7 Correct 2452 ms 14480 KB Output is correct
8 Correct 4350 ms 21848 KB Output is correct
9 Correct 1936 ms 18512 KB Output is correct
10 Execution timed out 8034 ms 32732 KB Time limit exceeded
11 Correct 3488 ms 20560 KB Output is correct
12 Correct 5968 ms 19532 KB Output is correct
13 Correct 5885 ms 20212 KB Output is correct
14 Execution timed out 8048 ms 20896 KB Time limit exceeded
15 Execution timed out 8054 ms 24296 KB Time limit exceeded
16 Correct 7115 ms 29804 KB Output is correct
17 Execution timed out 8101 ms 29924 KB Time limit exceeded