oj.uz

Submission #872432

# Submission time Handle Problem Language Result Execution time Memory
872432 2023-11-13T05:34:57 Z overwatch9 Regions (IOI09_regions) C++17
55 / 100
 5379 ms 102936 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[maxn];
int t = 0;
void dfs(int s) {
    visit[s] = t++;
    for (auto i : adj[s])
        dfs(i);
    finish[s] = t++;
}
int region_members_cnt = 0;
void dfs2(int s) {
    int id = big_region_id[region[s]];
    if (id != -1) {
        cnt[s][id] = 1;
    }
    for (auto i : adj[s]) {
        dfs2(i);
        for (int j = 0; j < region_members_cnt; j++) {
            cnt[s][j] += cnt[i][j];
            r1r2[id][j] += cnt[i][j];
        }
    }
}
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] = region_members_cnt++;
    }
    for (int i = 1; i <= n; i++) {
        cnt[i].resize(region_members_cnt);
        if (i < maxr)
            r1r2[i].resize(region_members_cnt);
    }

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

Compilation message

regions.cpp: In function 'int main()':
regions.cpp:69:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |             for (int j = 0; j < region_members[r2].size(); j++)
      |                             ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
regions.cpp:72:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |             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 4 ms 12888 KB Output is correct
5 Correct 7 ms 12888 KB Output is correct
6 Correct 11 ms 12888 KB Output is correct
7 Correct 16 ms 12888 KB Output is correct
8 Correct 19 ms 12888 KB Output is correct
9 Correct 33 ms 13144 KB Output is correct
10 Correct 58 ms 13144 KB Output is correct
11 Correct 110 ms 13400 KB Output is correct
12 Correct 109 ms 13860 KB Output is correct
13 Correct 162 ms 13284 KB Output is correct
14 Correct 270 ms 13952 KB Output is correct
15 Correct 232 ms 16320 KB Output is correct

Subtask #2
40.0 / 85.0

# Verdict Execution time Memory Grader output
1 Runtime error 56 ms 44748 KB Execution killed with signal 11
2 Runtime error 57 ms 43268 KB Execution killed with signal 11
3 Runtime error 61 ms 45600 KB Execution killed with signal 11
4 Correct 220 ms 14000 KB Output is correct
5 Correct 277 ms 15524 KB Output is correct
6 Correct 1540 ms 14804 KB Output is correct
7 Correct 1883 ms 15756 KB Output is correct
8 Correct 1364 ms 20116 KB Output is correct
9 Correct 2476 ms 19672 KB Output is correct
10 Correct 4693 ms 24260 KB Output is correct
11 Correct 5379 ms 18484 KB Output is correct
12 Runtime error 150 ms 54944 KB Execution killed with signal 11
13 Runtime error 147 ms 54832 KB Execution killed with signal 11
14 Runtime error 182 ms 83420 KB Execution killed with signal 11
15 Runtime error 142 ms 61296 KB Execution killed with signal 11
16 Runtime error 150 ms 74744 KB Execution killed with signal 11
17 Runtime error 181 ms 102936 KB Execution killed with signal 11