oj.uz

Submission #872190

# Submission time Handle Problem Language Result Execution time Memory
872190 2023-11-12T13:15:14 Z overwatch9 Regions (IOI09_regions) C++17
55 / 100
 8000 ms 56876 KB 
#include <iostream>
#include <unordered_map>
#include <set>
#include <vector>
#include <algorithm>
using namespace std;
const int maxn = 2e5;
int visit[maxn], finish[maxn], region[maxn];
vector <int> adj[maxn];
vector <int> region_members[maxn];
int t = 0;
void dfs(int s, int p) {
    visit[s] = t++;
    region_members[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() {
    // 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, 1);
    while (q--) {
        int r1, r2;
        cin >> r1 >> r2;
        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;
    }
}

Compilation message

regions.cpp: In function 'int main()':
regions.cpp:40:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |         for (int j = 0; j < region_members[r2].size(); j++)
      |                         ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
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 |         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 10840 KB Output is correct
2 Correct 2 ms 10840 KB Output is correct
3 Correct 3 ms 10840 KB Output is correct
4 Correct 4 ms 10840 KB Output is correct
5 Correct 5 ms 10840 KB Output is correct
6 Correct 10 ms 10840 KB Output is correct
7 Correct 14 ms 10840 KB Output is correct
8 Correct 18 ms 10840 KB Output is correct
9 Correct 29 ms 11096 KB Output is correct
10 Correct 52 ms 11096 KB Output is correct
11 Correct 76 ms 11352 KB Output is correct
12 Correct 95 ms 11716 KB Output is correct
13 Correct 123 ms 11544 KB Output is correct
14 Correct 198 ms 11908 KB Output is correct
15 Correct 232 ms 14356 KB Output is correct

Subtask #2
40.0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 8051 ms 14560 KB Time limit exceeded
2 Execution timed out 8057 ms 13368 KB Time limit exceeded
3 Execution timed out 8016 ms 16312 KB Time limit exceeded
4 Correct 198 ms 12092 KB Output is correct
5 Correct 267 ms 13656 KB Output is correct
6 Correct 1082 ms 13032 KB Output is correct
7 Correct 1359 ms 14032 KB Output is correct
8 Correct 1092 ms 18448 KB Output is correct
9 Correct 1912 ms 18240 KB Output is correct
10 Correct 3736 ms 22884 KB Output is correct
11 Runtime error 116 ms 33256 KB Execution killed with signal 11
12 Correct 7640 ms 19384 KB Output is correct
13 Execution timed out 8031 ms 19580 KB Time limit exceeded
14 Runtime error 116 ms 37900 KB Execution killed with signal 11
15 Runtime error 119 ms 44616 KB Execution killed with signal 11
16 Runtime error 122 ms 56876 KB Execution killed with signal 11
17 Runtime error 123 ms 54636 KB Execution killed with signal 11