oj.uz

Submission #872425

# Submission time Handle Problem Language Result Execution time Memory
872425 2023-11-13T05:17:48 Z overwatch9 Regions (IOI09_regions) C++17
55 / 100
 5034 ms 115736 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[region[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 2 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 4 ms 12888 KB Output is correct
5 Correct 6 ms 12888 KB Output is correct
6 Correct 10 ms 12888 KB Output is correct
7 Correct 18 ms 12888 KB Output is correct
8 Correct 19 ms 12888 KB Output is correct
9 Correct 27 ms 13912 KB Output is correct
10 Correct 62 ms 13144 KB Output is correct
11 Correct 99 ms 13420 KB Output is correct
12 Correct 107 ms 14256 KB Output is correct
13 Correct 147 ms 13416 KB Output is correct
14 Correct 272 ms 13992 KB Output is correct
15 Correct 229 ms 21308 KB Output is correct

Subtask #2
40.0 / 85.0

# Verdict Execution time Memory Grader output
1 Runtime error 79 ms 38292 KB Execution killed with signal 8
2 Runtime error 67 ms 30752 KB Execution killed with signal 8
3 Runtime error 96 ms 48952 KB Execution killed with signal 8
4 Correct 235 ms 14192 KB Output is correct
5 Correct 276 ms 18872 KB Output is correct
6 Correct 1507 ms 15536 KB Output is correct
7 Correct 1793 ms 16080 KB Output is correct
8 Correct 1345 ms 28480 KB Output is correct
9 Correct 2499 ms 21660 KB Output is correct
10 Correct 4601 ms 34960 KB Output is correct
11 Correct 5034 ms 18496 KB Output is correct
12 Runtime error 155 ms 41500 KB Execution killed with signal 8
13 Runtime error 141 ms 46580 KB Execution killed with signal 8
14 Runtime error 213 ms 42460 KB Execution killed with signal 8
15 Runtime error 168 ms 69312 KB Execution killed with signal 8
16 Runtime error 198 ms 115736 KB Execution killed with signal 8
17 Runtime error 350 ms 113068 KB Execution killed with signal 8