oj.uz

Submission #872170

# Submission time Handle Problem Language Result Execution time Memory
872170 2023-11-12T12:13:07 Z overwatch9 Regions (IOI09_regions) C++17
0 / 100
 1752 ms 56976 KB 
#include <iostream>
#include <unordered_map>
#include <set>
#include <vector>
using namespace std;
const int maxn = 2e5;
int visit[maxn], finish[maxn], region[maxn];
vector <int> adj[maxn];
vector <int> regions[maxn];
int t = 0;
void dfs(int s, int p) {
    visit[s] = t++;
    regions[region[s]].push_back(s);
    for (auto i : adj[s])
        dfs(i, s);
    finish[s] = t;
}
bool is_ancestor(int a, int b) {
    return visit[a] <= visit[b] && finish[a] >= finish[b];
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    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, 1);
    while (q--) {
        int r1, r2;
        cin >> r1 >> r2;
        int ans = 0;
        int p1 = 0, p2 = 0;
        int moved = 0;
        while (p1 < regions[r1].size() && p2 < regions[r2].size()) {
            if (is_ancestor(regions[r1][p1], regions[r2][p2])) {
                while (p2 < regions[r2].size() && is_ancestor(regions[r1][p1], regions[r2][p2])) {
                    p2++;
                    moved++;
                }
                ans += moved;
            } else if (is_ancestor(regions[r2][p2], regions[r1][p1])) {
                while (p2 < regions[r2].size() && is_ancestor(regions[r2][p2], regions[r1][p1])) {
                    p2++;
                    moved = 0;
                }
            } else {
                p1++;
                moved = 0;
            }
        }
        cout << ans << endl;
    }
}

Compilation message

regions.cpp: In function 'int main()':
regions.cpp:41:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |         while (p1 < regions[r1].size() && p2 < regions[r2].size()) {
      |                ~~~^~~~~~~~~~~~~~~~~~~~
regions.cpp:41:46: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |         while (p1 < regions[r1].size() && p2 < regions[r2].size()) {
      |                                           ~~~^~~~~~~~~~~~~~~~~~~~
regions.cpp:43:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |                 while (p2 < regions[r2].size() && is_ancestor(regions[r1][p1], regions[r2][p2])) {
      |                        ~~~^~~~~~~~~~~~~~~~~~~~
regions.cpp:49:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |                 while (p2 < regions[r2].size() && is_ancestor(regions[r2][p2], regions[r1][p1])) {
      |                        ~~~^~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 10840 KB Output isn't correct
2 Incorrect 2 ms 10840 KB Output isn't correct
3 Incorrect 3 ms 10840 KB Output isn't correct
4 Incorrect 3 ms 10840 KB Output isn't correct
5 Incorrect 6 ms 10840 KB Output isn't correct
6 Incorrect 10 ms 10864 KB Output isn't correct
7 Incorrect 14 ms 10840 KB Output isn't correct
8 Incorrect 15 ms 10840 KB Output isn't correct
9 Incorrect 25 ms 11352 KB Output isn't correct
10 Incorrect 40 ms 11096 KB Output isn't correct
11 Incorrect 41 ms 11356 KB Output isn't correct
12 Incorrect 49 ms 11920 KB Output isn't correct
13 Incorrect 58 ms 11372 KB Output isn't correct
14 Incorrect 86 ms 11912 KB Output isn't correct
15 Incorrect 92 ms 14424 KB Output isn't correct

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 779 ms 14572 KB Output isn't correct
2 Incorrect 883 ms 13388 KB Output isn't correct
3 Incorrect 1752 ms 16276 KB Output isn't correct
4 Incorrect 124 ms 11864 KB Output isn't correct
5 Incorrect 185 ms 13396 KB Output isn't correct
6 Incorrect 329 ms 13040 KB Output isn't correct
7 Incorrect 479 ms 13696 KB Output isn't correct
8 Incorrect 488 ms 18336 KB Output isn't correct
9 Incorrect 760 ms 18304 KB Output isn't correct
10 Incorrect 1075 ms 23100 KB Output isn't correct
11 Runtime error 54 ms 33132 KB Execution killed with signal 11
12 Incorrect 462 ms 19444 KB Output isn't correct
13 Incorrect 672 ms 19828 KB Output isn't correct
14 Runtime error 70 ms 37736 KB Execution killed with signal 11
15 Runtime error 56 ms 44764 KB Execution killed with signal 11
16 Runtime error 72 ms 56976 KB Execution killed with signal 11
17 Runtime error 62 ms 54856 KB Execution killed with signal 11