oj.uz

Submission #872204

# Submission time Handle Problem Language Result Execution time Memory
872204 2023-11-12T13:46:52 Z overwatch9 Regions (IOI09_regions) C++17
1 / 100
 8000 ms 61344 KB 
#include <iostream>
#include <map>
#include <set>
#include <vector>
#include <algorithm>
using namespace std;
const int maxn = 2e5 + 1;
const int maxr = 5 + 1;
int visit[maxn], finish[maxn], region[maxn];
vector <int> adj[maxn];
vector <int> region_members[maxn];
int r1r2[maxr][maxr];
int t = 0;
void dfs(int s) {
    visit[s] = t++;
    region_members[region[s]].push_back(s);
    for (auto i : adj[s])
        dfs(i);
    finish[s] = t++;
}
map <int, int> dfs2(int s) {
    map <int, int> ans;
    ans[region[s]] = 1;
    for (auto i : adj[s]) {
        auto res = dfs2(i);
        for (auto j : res) {
            ans[j.first] += j.second;
            r1r2[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];
    for (int i = 2; i <= n; i++) {
        int x;
        cin >> x;
        adj[x].push_back(i);
        cin >> region[i];
    }
    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 {
            cout << r1r2[r1][r2] << endl;
        }
    }
}

Compilation message

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

Subtask #1
1.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 10840 KB Output is correct
2 Runtime error 12 ms 21632 KB Execution killed with signal 11
3 Runtime error 10 ms 21636 KB Execution killed with signal 11
4 Runtime error 11 ms 21724 KB Execution killed with signal 11
5 Runtime error 14 ms 21684 KB Execution killed with signal 11
6 Runtime error 25 ms 22096 KB Execution killed with signal 11
7 Runtime error 25 ms 21736 KB Execution killed with signal 11
8 Runtime error 30 ms 22056 KB Execution killed with signal 11
9 Runtime error 105 ms 24196 KB Execution killed with signal 11
10 Runtime error 41 ms 22652 KB Execution killed with signal 11
11 Runtime error 68 ms 23240 KB Execution killed with signal 11
12 Runtime error 349 ms 25260 KB Execution killed with signal 11
13 Runtime error 73 ms 23108 KB Execution killed with signal 11
14 Runtime error 123 ms 24264 KB Execution killed with signal 11
15 Runtime error 595 ms 42784 KB Execution killed with signal 11

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Runtime error 976 ms 34668 KB Execution killed with signal 11
2 Runtime error 648 ms 27644 KB Execution killed with signal 11
3 Runtime error 1727 ms 44732 KB Execution killed with signal 11
4 Runtime error 562 ms 25264 KB Execution killed with signal 11
5 Runtime error 3588 ms 36172 KB Execution killed with signal 11
6 Runtime error 2469 ms 29592 KB Execution killed with signal 11
7 Runtime error 3727 ms 31144 KB Execution killed with signal 11
8 Execution timed out 8025 ms 30440 KB Time limit exceeded
9 Execution timed out 8013 ms 22532 KB Time limit exceeded
10 Execution timed out 8042 ms 26432 KB Time limit exceeded
11 Runtime error 5719 ms 40860 KB Execution killed with signal 11
12 Runtime error 4609 ms 43928 KB Execution killed with signal 11
13 Execution timed out 8087 ms 23740 KB Time limit exceeded
14 Execution timed out 8039 ms 22624 KB Time limit exceeded
15 Execution timed out 8023 ms 35332 KB Time limit exceeded
16 Execution timed out 8077 ms 61344 KB Time limit exceeded
17 Execution timed out 8013 ms 56208 KB Time limit exceeded