oj.uz

Submission #872423

# Submission time Handle Problem Language Result Execution time Memory
872423 2023-11-13T05:14:38 Z overwatch9 Regions (IOI09_regions) C++17
55 / 100
 4838 ms 115724 KB 
#include <iostream>
#include <set>
#include <vector>
#include <algorithm>
#include <unordered_map>
using namespace std;
const int maxn = 2e5 + 1;
const int maxr = 500 + 1;
int visit[maxn], finish[maxn], region[maxn];
vector <int> adj[maxn];
vector <int> region_members[maxn];
int big_region_id[maxn];
vector <unordered_map <int, int>> r1r2;
int t = 0;
void dfs(int s) {
    visit[s] = t++;
    for (auto i : adj[s])
        dfs(i);
    finish[s] = t++;
}
unordered_map <int, int> dfs2(int s) {
    unordered_map <int, int> ans;
    if (big_region_id[region[s]] != -1) {
        ans[big_region_id[region[s]]] = 1;
    }
    for (auto i : adj[s]) {
        auto res = dfs2(i);
        for (auto j : res) {
            ans[j.first] += j.second;
            if (big_region_id[s] != -1)
                r1r2[big_region_id[region[s]]][j.first] += j.second;
        }
    }
    return ans;
}
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 + maxn, -1);
    int region_members_cnt = 0;
    for (int i = 1; i <= r; i++) {
        if (region_members[i].size() > 500)
            big_region_id[i] = region_members_cnt++;
    }
    r1r2.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';
        }
    }
}

Compilation message

regions.cpp: In function 'int main()':
regions.cpp:66:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |             for (int j = 0; j < region_members[r2].size(); j++)
      |                             ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
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 i = 0; i < region_members[r1].size(); i++) {
      |                             ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 12888 KB Output is correct
2 Correct 3 ms 12888 KB Output is correct
3 Correct 4 ms 12888 KB Output is correct
4 Correct 5 ms 13140 KB Output is correct
5 Correct 6 ms 12888 KB Output is correct
6 Correct 13 ms 12884 KB Output is correct
7 Correct 17 ms 12888 KB Output is correct
8 Correct 23 ms 12888 KB Output is correct
9 Correct 38 ms 13912 KB Output is correct
10 Correct 62 ms 13144 KB Output is correct
11 Correct 97 ms 13400 KB Output is correct
12 Correct 108 ms 14360 KB Output is correct
13 Correct 155 ms 13244 KB Output is correct
14 Correct 290 ms 13992 KB Output is correct
15 Correct 249 ms 21308 KB Output is correct

Subtask #2
40.0 / 85.0

# Verdict Execution time Memory Grader output
1 Runtime error 58 ms 33720 KB Execution killed with signal 8
2 Runtime error 53 ms 29996 KB Execution killed with signal 8
3 Runtime error 89 ms 48944 KB Execution killed with signal 8
4 Correct 234 ms 14200 KB Output is correct
5 Correct 272 ms 18680 KB Output is correct
6 Correct 1562 ms 15344 KB Output is correct
7 Correct 1934 ms 16072 KB Output is correct
8 Correct 1488 ms 28488 KB Output is correct
9 Correct 2617 ms 21664 KB Output is correct
10 Correct 4632 ms 34960 KB Output is correct
11 Correct 4838 ms 18468 KB Output is correct
12 Runtime error 121 ms 40508 KB Execution killed with signal 8
13 Runtime error 114 ms 40296 KB Execution killed with signal 8
14 Runtime error 125 ms 39640 KB Execution killed with signal 8
15 Runtime error 151 ms 69344 KB Execution killed with signal 8
16 Runtime error 207 ms 115724 KB Execution killed with signal 8
17 Runtime error 118 ms 52264 KB Execution killed with signal 8