oj.uz

Submission #872430

# Submission time Handle Problem Language Result Execution time Memory
872430 2023-11-13T05:34:02 Z overwatch9 Regions (IOI09_regions) C++17
13 / 100
 147 ms 52436 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++) {
        r1r2[i].resize(region_members_cnt);
        if (i < maxr)
            cnt[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
13.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 6 ms 12888 KB Output is correct
6 Correct 10 ms 12936 KB Output is correct
7 Correct 16 ms 12888 KB Output is correct
8 Correct 18 ms 12888 KB Output is correct
9 Correct 28 ms 13144 KB Output is correct
10 Correct 56 ms 13144 KB Output is correct
11 Correct 95 ms 13400 KB Output is correct
12 Correct 103 ms 13848 KB Output is correct
13 Correct 147 ms 13468 KB Output is correct
14 Runtime error 27 ms 27772 KB Execution killed with signal 11
15 Runtime error 31 ms 31268 KB Execution killed with signal 11

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Runtime error 47 ms 37392 KB Execution killed with signal 11
2 Runtime error 49 ms 36104 KB Execution killed with signal 11
3 Runtime error 52 ms 37076 KB Execution killed with signal 11
4 Runtime error 26 ms 27784 KB Execution killed with signal 11
5 Runtime error 31 ms 30968 KB Execution killed with signal 11
6 Runtime error 42 ms 29620 KB Execution killed with signal 11
7 Runtime error 50 ms 30856 KB Execution killed with signal 11
8 Runtime error 63 ms 38164 KB Execution killed with signal 11
9 Runtime error 91 ms 38904 KB Execution killed with signal 11
10 Runtime error 102 ms 45808 KB Execution killed with signal 11
11 Runtime error 123 ms 37340 KB Execution killed with signal 11
12 Runtime error 106 ms 43312 KB Execution killed with signal 11
13 Runtime error 106 ms 42204 KB Execution killed with signal 11
14 Runtime error 126 ms 48620 KB Execution killed with signal 11
15 Runtime error 113 ms 44720 KB Execution killed with signal 11
16 Runtime error 111 ms 44776 KB Execution killed with signal 11
17 Runtime error 115 ms 52436 KB Execution killed with signal 11