oj.uz

Submission #872207

# Submission time Handle Problem Language Result Execution time Memory
872207 2023-11-12T13:49:49 Z overwatch9 Regions (IOI09_regions) C++17
40 / 100
 5233 ms 130816 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;
    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:54:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |             for (int j = 0; j < region_members[r2].size(); j++)
      |                             ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
regions.cpp:57:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |             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 4 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 18 ms 19032 KB Output is correct
7 Correct 17 ms 16984 KB Output is correct
8 Correct 25 ms 16984 KB Output is correct
9 Correct 96 ms 20056 KB Output is correct
10 Correct 72 ms 21336 KB Output is correct
11 Correct 118 ms 19540 KB Output is correct
12 Correct 377 ms 24876 KB Output is correct
13 Correct 127 ms 21620 KB Output is correct
14 Correct 220 ms 18116 KB Output is correct
15 Correct 700 ms 29268 KB Output is correct

Subtask #2
25.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 3595 ms 23148 KB Output is correct
2 Correct 3467 ms 21796 KB Output is correct
3 Correct 5233 ms 30156 KB Output is correct
4 Correct 615 ms 94428 KB Output is correct
5 Correct 3644 ms 116340 KB Output is correct
6 Runtime error 54 ms 42204 KB Execution killed with signal 11
7 Runtime error 48 ms 30968 KB Execution killed with signal 11
8 Runtime error 66 ms 40960 KB Execution killed with signal 11
9 Runtime error 97 ms 39520 KB Execution killed with signal 11
10 Runtime error 107 ms 53216 KB Execution killed with signal 11
11 Runtime error 126 ms 38084 KB Execution killed with signal 11
12 Runtime error 124 ms 41276 KB Execution killed with signal 11
13 Runtime error 115 ms 41724 KB Execution killed with signal 11
14 Runtime error 126 ms 49380 KB Execution killed with signal 11
15 Runtime error 124 ms 54944 KB Execution killed with signal 11
16 Runtime error 177 ms 130816 KB Execution killed with signal 11
17 Runtime error 136 ms 58004 KB Execution killed with signal 11