oj.uz

Submission #872205

# Submission time Handle Problem Language Result Execution time Memory
872205 2023-11-12T13:47:20 Z overwatch9 Regions (IOI09_regions) C++17
30 / 100
 2768 ms 125832 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;
    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
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 12632 KB Output is correct
4 Correct 4 ms 12632 KB Output is correct
5 Correct 7 ms 12632 KB Output is correct
6 Correct 19 ms 12888 KB Output is correct
7 Correct 19 ms 12888 KB Output is correct
8 Correct 27 ms 12888 KB Output is correct
9 Correct 101 ms 14168 KB Output is correct
10 Correct 75 ms 13416 KB Output is correct
11 Correct 119 ms 13656 KB Output is correct
12 Correct 401 ms 15004 KB Output is correct
13 Correct 130 ms 13324 KB Output is correct
14 Correct 244 ms 14148 KB Output is correct
15 Correct 689 ms 23172 KB Output is correct

Subtask #2
15.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1417 ms 18972 KB Output is correct
2 Correct 1148 ms 15500 KB Output is correct
3 Correct 2768 ms 23864 KB Output is correct
4 Runtime error 31 ms 27768 KB Execution killed with signal 11
5 Runtime error 41 ms 30964 KB Execution killed with signal 11
6 Runtime error 37 ms 29252 KB Execution killed with signal 11
7 Runtime error 67 ms 30804 KB Execution killed with signal 11
8 Runtime error 75 ms 40496 KB Execution killed with signal 11
9 Runtime error 101 ms 38476 KB Execution killed with signal 11
10 Runtime error 103 ms 48108 KB Execution killed with signal 11
11 Runtime error 119 ms 36704 KB Execution killed with signal 11
12 Runtime error 123 ms 40380 KB Execution killed with signal 11
13 Runtime error 118 ms 40816 KB Execution killed with signal 11
14 Runtime error 136 ms 40052 KB Execution killed with signal 11
15 Runtime error 139 ms 49916 KB Execution killed with signal 11
16 Runtime error 197 ms 125832 KB Execution killed with signal 11
17 Runtime error 140 ms 57252 KB Execution killed with signal 11