oj.uz

Submission #872428

# Submission time Handle Problem Language Result Execution time Memory
872428 2023-11-13T05:32:37 Z overwatch9 Regions (IOI09_regions) C++17
55 / 100
 5240 ms 103216 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[maxn];
vector <int> cnt[maxr];
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
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12888 KB Output is correct
2 Correct 3 ms 12888 KB Output is correct
3 Correct 3 ms 12728 KB Output is correct
4 Correct 5 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 17 ms 12888 KB Output is correct
8 Correct 20 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 112 ms 13408 KB Output is correct
12 Correct 105 ms 13876 KB Output is correct
13 Correct 157 ms 13460 KB Output is correct
14 Correct 293 ms 13952 KB Output is correct
15 Correct 231 ms 16384 KB Output is correct

Subtask #2
40.0 / 85.0

# Verdict Execution time Memory Grader output
1 Runtime error 59 ms 45040 KB Execution killed with signal 11
2 Runtime error 56 ms 43324 KB Execution killed with signal 11
3 Runtime error 64 ms 45608 KB Execution killed with signal 11
4 Correct 220 ms 14252 KB Output is correct
5 Correct 288 ms 15524 KB Output is correct
6 Correct 1561 ms 14664 KB Output is correct
7 Correct 1922 ms 15744 KB Output is correct
8 Correct 1380 ms 20100 KB Output is correct
9 Correct 2535 ms 19672 KB Output is correct
10 Correct 4971 ms 24496 KB Output is correct
11 Correct 5240 ms 18784 KB Output is correct
12 Runtime error 149 ms 54976 KB Execution killed with signal 11
13 Runtime error 133 ms 54864 KB Execution killed with signal 11
14 Runtime error 161 ms 83360 KB Execution killed with signal 11
15 Runtime error 129 ms 61236 KB Execution killed with signal 11
16 Runtime error 148 ms 74744 KB Execution killed with signal 11
17 Runtime error 158 ms 103216 KB Execution killed with signal 11