oj.uz

Submission #872208

# Submission time Handle Problem Language Result Execution time Memory
872208 2023-11-12T13:54:04 Z overwatch9 Regions (IOI09_regions) C++17
40 / 100
 5432 ms 116544 KB 
#include <iostream>
#include <map>
#include <set>
#include <vector>
#include <algorithm>
using namespace std;
const int maxn = 2e5 + 1;
const int maxr = 5000 + 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 4 ms 12632 KB Output is correct
2 Correct 3 ms 12740 KB Output is correct
3 Correct 3 ms 14680 KB Output is correct
4 Correct 5 ms 14680 KB Output is correct
5 Correct 7 ms 14680 KB Output is correct
6 Correct 21 ms 19032 KB Output is correct
7 Correct 18 ms 16984 KB Output is correct
8 Correct 27 ms 16984 KB Output is correct
9 Correct 100 ms 20208 KB Output is correct
10 Correct 72 ms 21488 KB Output is correct
11 Correct 124 ms 19544 KB Output is correct
12 Correct 357 ms 24784 KB Output is correct
13 Correct 135 ms 21432 KB Output is correct
14 Correct 235 ms 18072 KB Output is correct
15 Correct 675 ms 29512 KB Output is correct

Subtask #2
25.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 3669 ms 23148 KB Output is correct
2 Correct 3418 ms 21756 KB Output is correct
3 Correct 5432 ms 30200 KB Output is correct
4 Correct 613 ms 94564 KB Output is correct
5 Correct 3608 ms 116544 KB Output is correct
6 Runtime error 49 ms 42064 KB Execution killed with signal 11
7 Runtime error 50 ms 31156 KB Execution killed with signal 11
8 Runtime error 67 ms 40608 KB Execution killed with signal 11
9 Runtime error 92 ms 39656 KB Execution killed with signal 11
10 Runtime error 107 ms 52972 KB Execution killed with signal 11
11 Runtime error 127 ms 37720 KB Execution killed with signal 11
12 Runtime error 120 ms 45488 KB Execution killed with signal 11
13 Runtime error 121 ms 41760 KB Execution killed with signal 11
14 Runtime error 129 ms 49236 KB Execution killed with signal 11
15 Runtime error 123 ms 49560 KB Execution killed with signal 11
16 Runtime error 164 ms 112128 KB Execution killed with signal 11
17 Runtime error 125 ms 58016 KB Execution killed with signal 11