oj.uz

Submission #872435

# Submission time Handle Problem Language Result Execution time Memory
872435 2023-11-13T06:00:36 Z overwatch9 Regions (IOI09_regions) C++17
55 / 100
 4959 ms 102836 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);
    dfs2(1, 1);
    while (q--) {
        int r1, r2;
        cin >> r1 >> r2;
        if (big_region_id[r1] == -1) {
            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 if (big_region_id[r2] != -1) {
            int a = big_region_id[r1];
            int b = big_region_id[r2];
            cout << r1r2[a][b] << '\n';
        } else {
            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: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 j = 0; j < region_members[r2].size(); j++)
      |                             ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
regions.cpp:75:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |             for (int i = 0; i < region_members[r1].size(); i++) {
      |                             ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12888 KB Output is correct
2 Correct 2 ms 12888 KB Output is correct
3 Correct 3 ms 13140 KB Output is correct
4 Correct 4 ms 12888 KB Output is correct
5 Correct 6 ms 12888 KB Output is correct
6 Correct 15 ms 12888 KB Output is correct
7 Correct 18 ms 12888 KB Output is correct
8 Correct 20 ms 12888 KB Output is correct
9 Correct 27 ms 13568 KB Output is correct
10 Correct 62 ms 13144 KB Output is correct
11 Correct 98 ms 13572 KB Output is correct
12 Correct 110 ms 14076 KB Output is correct
13 Correct 154 ms 13340 KB Output is correct
14 Correct 274 ms 13968 KB Output is correct
15 Correct 211 ms 18200 KB Output is correct

Subtask #2
40.0 / 85.0

# Verdict Execution time Memory Grader output
1 Runtime error 59 ms 44736 KB Execution killed with signal 11
2 Runtime error 61 ms 43500 KB Execution killed with signal 11
3 Runtime error 63 ms 45656 KB Execution killed with signal 11
4 Correct 236 ms 14072 KB Output is correct
5 Correct 275 ms 16948 KB Output is correct
6 Correct 1536 ms 15072 KB Output is correct
7 Correct 1793 ms 15984 KB Output is correct
8 Correct 1389 ms 23296 KB Output is correct
9 Correct 2441 ms 20536 KB Output is correct
10 Correct 4703 ms 28424 KB Output is correct
11 Correct 4959 ms 18852 KB Output is correct
12 Runtime error 130 ms 55008 KB Execution killed with signal 11
13 Runtime error 122 ms 54876 KB Execution killed with signal 11
14 Runtime error 154 ms 83324 KB Execution killed with signal 11
15 Runtime error 129 ms 61408 KB Execution killed with signal 11
16 Runtime error 135 ms 68652 KB Execution killed with signal 11
17 Runtime error 153 ms 102836 KB Execution killed with signal 11