oj.uz

Submission #872461

# Submission time Handle Problem Language Result Execution time Memory
872461 2023-11-13T07:01:06 Z overwatch9 Regions (IOI09_regions) C++17
55 / 100
 3877 ms 106708 KB 
#include <iostream>
#include <set>
#include <vector>
#include <algorithm>
#include <unordered_map>
using namespace std;
const int maxn = 2e5 + 1;
const int maxr = 25000 + 1;
int visit[maxn], finish[maxn], region[maxn];
vector <int> adj[maxn];
vector <int> region_members[maxr];
int big_region_id[maxr];
vector <int> r1r2[maxr];
vector <int> cnt_parents[maxn];
int t = 0;
void dfs(int s) {
    visit[s] = t++;
    for (auto i : adj[s])
        dfs(i);
    finish[s] = t++;
}
int big_region_cnt = 0;
void dfs2(int s, int p) {
    int id1 = big_region_id[region[s]];
    int id2 = big_region_id[region[p]];
    if (s != p) {
        cnt_parents[s] = cnt_parents[p];
        if (id2 != -1)
            cnt_parents[s][id2]++;
    }
    if (id1 != -1) {
        for (int i = 0; i < big_region_cnt; i++)
            r1r2[i][id1] += cnt_parents[s][i];
    }
    for (auto i : adj[s]) {
        dfs2(i, s);
    }
}
int main() {
    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    int n, r, q;
    cin >> n >> r >> q;
    cin >> region[1];
    region_members[region[1]].push_back(1);
    for (int i = 2; i <= n; i++) {
        int x;
        cin >> x;
        adj[x].push_back(i);
        cin >> region[i];
        region_members[region[i]].push_back(i);
    }
    fill(big_region_id, big_region_id + maxr, -1);
    for (int i = 1; i <= r; i++) {
        if (region_members[i].size() > 500)
            big_region_id[i] = big_region_cnt++;
    }   
    for (int i = 1; i <= n; i++) {
        cnt_parents[i].resize(big_region_cnt);
        if (i < maxr)
            r1r2[i].resize(big_region_cnt);
    }
    dfs(1);
    vector <vector <int>> starts(r+1);
    for (int i = 1; i <= r; i++) {
        for (auto j : region_members[i])
            starts[i].push_back(visit[j]);
        sort(starts[i].begin(), starts[i].end());
    }

    dfs2(1, 1);
    while (q--) {
        int r1, r2;
        cin >> r1 >> r2;
        if (big_region_id[r1] == -1) { // r1 = small
            int ans = 0;
            vector <int> &st = starts[r2];
            for (int i = 0; i < region_members[r1].size(); i++) {
                auto l = upper_bound(st.begin(), st.end(), visit[region_members[r1][i]]);
                auto r = upper_bound(st.begin(), st.end(), finish[region_members[r1][i]]);
                if (r == st.begin())
                    continue;
                r--;
                int id1 = l - st.begin();
                int id2 = r - st.begin();
                ans += max(0, (id2 - id1 + 1));
            }
            cout << ans << endl;
        } else if (big_region_id[r2] != -1) { // r2 = big
            int a = big_region_id[r1];
            int b = big_region_id[r2];
            cout << r1r2[a][b] << '\n';
        } else { // r1 = big, r2 = small
            int ans = 0;
            for (auto i : region_members[r2])
                ans += cnt_parents[i][big_region_id[r1]];
        }
    }
    return 0;
}

Compilation message

regions.cpp: In function 'int main()':
regions.cpp:78:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |             for (int i = 0; i < region_members[r1].size(); i++) {
      |                             ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12888 KB Output is correct
2 Correct 2 ms 12888 KB Output is correct
3 Correct 3 ms 12888 KB Output is correct
4 Correct 5 ms 12888 KB Output is correct
5 Correct 5 ms 12888 KB Output is correct
6 Correct 10 ms 12888 KB Output is correct
7 Correct 17 ms 12888 KB Output is correct
8 Correct 17 ms 12888 KB Output is correct
9 Correct 28 ms 13400 KB Output is correct
10 Correct 49 ms 13652 KB Output is correct
11 Correct 83 ms 13400 KB Output is correct
12 Correct 95 ms 14136 KB Output is correct
13 Correct 127 ms 13436 KB Output is correct
14 Correct 219 ms 13912 KB Output is correct
15 Correct 195 ms 18244 KB Output is correct

Subtask #2
40.0 / 85.0

# Verdict Execution time Memory Grader output
1 Runtime error 59 ms 45696 KB Execution killed with signal 11
2 Runtime error 65 ms 44068 KB Execution killed with signal 11
3 Runtime error 64 ms 46580 KB Execution killed with signal 11
4 Correct 178 ms 14380 KB Output is correct
5 Correct 242 ms 17008 KB Output is correct
6 Correct 1122 ms 15548 KB Output is correct
7 Correct 1324 ms 16300 KB Output is correct
8 Correct 1041 ms 24164 KB Output is correct
9 Correct 1785 ms 22112 KB Output is correct
10 Correct 3737 ms 30280 KB Output is correct
11 Correct 3877 ms 20980 KB Output is correct
12 Runtime error 142 ms 58076 KB Execution killed with signal 11
13 Runtime error 131 ms 57916 KB Execution killed with signal 11
14 Runtime error 170 ms 87160 KB Execution killed with signal 11
15 Runtime error 154 ms 65756 KB Execution killed with signal 11
16 Runtime error 148 ms 73300 KB Execution killed with signal 11
17 Runtime error 164 ms 106708 KB Execution killed with signal 11