oj.uz

Submission #872210

# Submission time Handle Problem Language Result Execution time Memory
872210 2023-11-12T13:54:58 Z overwatch9 Regions (IOI09_regions) C++17
30 / 100
 5204 ms 107952 KB 
#include <iostream>
#include <map>
#include <set>
#include <vector>
#include <algorithm>
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 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;
    if (region[s] < maxr)
        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) {
            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:55:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |             for (int j = 0; j < region_members[r2].size(); j++)
      |                             ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
regions.cpp:58:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |             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 12632 KB Output is correct
2 Correct 2 ms 12632 KB Output is correct
3 Correct 3 ms 12632 KB Output is correct
4 Correct 4 ms 12716 KB Output is correct
5 Correct 7 ms 12884 KB Output is correct
6 Correct 18 ms 12888 KB Output is correct
7 Correct 18 ms 12888 KB Output is correct
8 Correct 32 ms 12888 KB Output is correct
9 Correct 100 ms 14168 KB Output is correct
10 Correct 61 ms 13400 KB Output is correct
11 Correct 121 ms 13656 KB Output is correct
12 Correct 357 ms 14680 KB Output is correct
13 Correct 138 ms 13560 KB Output is correct
14 Correct 235 ms 14168 KB Output is correct
15 Correct 680 ms 23172 KB Output is correct

Subtask #2
15.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 3705 ms 19060 KB Output is correct
2 Correct 3472 ms 15512 KB Output is correct
3 Correct 5204 ms 23864 KB Output is correct
4 Runtime error 26 ms 27712 KB Execution killed with signal 11
5 Runtime error 32 ms 30756 KB Execution killed with signal 11
6 Runtime error 37 ms 29292 KB Execution killed with signal 11
7 Runtime error 48 ms 30732 KB Execution killed with signal 11
8 Runtime error 68 ms 39680 KB Execution killed with signal 11
9 Runtime error 92 ms 38688 KB Execution killed with signal 11
10 Runtime error 105 ms 47852 KB Execution killed with signal 11
11 Runtime error 117 ms 36712 KB Execution killed with signal 11
12 Runtime error 117 ms 40528 KB Execution killed with signal 11
13 Runtime error 112 ms 40832 KB Execution killed with signal 11
14 Runtime error 122 ms 40032 KB Execution killed with signal 11
15 Runtime error 147 ms 48604 KB Execution killed with signal 11
16 Runtime error 162 ms 107952 KB Execution killed with signal 11
17 Runtime error 121 ms 57252 KB Execution killed with signal 11