oj.uz

Submission #872470

# Submission time Handle Problem Language Result Execution time Memory
872470 2023-11-13T07:28:42 Z overwatch9 Regions (IOI09_regions) C++17
55 / 100
 3990 ms 101096 KB 
#include <iostream>
#include <set>
#include <vector>
#include <algorithm>
#include <unordered_map>
using namespace std;
const int maxn = 2e5 + 10;
const int maxr = 25000 + 10;
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]];
    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 (int i = 0; i < adj[s].size(); i++)
        dfs2(adj[s][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 <= big_region_cnt)
            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 'void dfs2(int, int)':
regions.cpp:33:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |     for (int i = 0; i < adj[s].size(); i++)
      |                     ~~^~~~~~~~~~~~~~~
regions.cpp: In function 'int main()':
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 13064 KB Output is correct
2 Correct 2 ms 12888 KB Output is correct
3 Correct 6 ms 12912 KB Output is correct
4 Correct 4 ms 12888 KB Output is correct
5 Correct 6 ms 12888 KB Output is correct
6 Correct 12 ms 12888 KB Output is correct
7 Correct 16 ms 12888 KB Output is correct
8 Correct 20 ms 12972 KB Output is correct
9 Correct 28 ms 13400 KB Output is correct
10 Correct 54 ms 13144 KB Output is correct
11 Correct 86 ms 13400 KB Output is correct
12 Correct 95 ms 14080 KB Output is correct
13 Correct 136 ms 13400 KB Output is correct
14 Correct 231 ms 14080 KB Output is correct
15 Correct 207 ms 18416 KB Output is correct

Subtask #2
40.0 / 85.0

# Verdict Execution time Memory Grader output
1 Runtime error 61 ms 42372 KB Execution killed with signal 11
2 Runtime error 57 ms 40940 KB Execution killed with signal 11
3 Runtime error 66 ms 44244 KB Execution killed with signal 11
4 Correct 208 ms 14296 KB Output is correct
5 Correct 243 ms 16948 KB Output is correct
6 Correct 1138 ms 15548 KB Output is correct
7 Correct 1375 ms 16464 KB Output is correct
8 Correct 1012 ms 24112 KB Output is correct
9 Correct 1903 ms 21936 KB Output is correct
10 Correct 3755 ms 30296 KB Output is correct
11 Correct 3990 ms 20980 KB Output is correct
12 Runtime error 157 ms 56400 KB Execution killed with signal 11
13 Runtime error 133 ms 56228 KB Execution killed with signal 11
14 Runtime error 182 ms 82476 KB Execution killed with signal 11
15 Runtime error 140 ms 64112 KB Execution killed with signal 11
16 Runtime error 143 ms 71148 KB Execution killed with signal 11
17 Runtime error 171 ms 101096 KB Execution killed with signal 11