oj.uz

Submission #867751

# Submission time Handle Problem Language Result Execution time Memory
867751 2023-10-29T12:18:00 Z overwatch9 Regions (IOI09_regions) C++17
30 / 100
 3640 ms 131072 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
using namespace std;
vector <vector <int>> adj;
vector <int> col;
vector <vector <int>> ans;
vector <vector <int>> freq, regions;
int n, r, q;
void dfs(int s, int p) {
    freq[s][col[s]]++;
    for (auto i : adj[s]) {
        if (i == p)
            continue;
        dfs(i, s);
        for (int j = 1; j <= r; j++)
            freq[s][j] += freq[i][j];
    }
}
int main() {
    cin >> n >> r >> q;
    col = vector <int> (n+1);
    adj.resize(n+1);
    ans.resize(n+1);
    freq = vector <vector <int>> (n+1, vector <int> (r+1));
    regions.resize(n+1);

    cin >> col[1];
    regions[col[1]].push_back(1);
    for (int i = 2; i <= n; i++) {
        int p, c;
        cin >> p >> c;
        adj[i].push_back(p);
        adj[p].push_back(i);
        col[i] = c;
        regions[col[i]].push_back(i);
    }
    dfs(1, 1);
    while (q--) {
        int r1, r2;
        cin >> r1 >> r2;
        int ans = 0;
        for (auto i : regions[r1])
            ans += freq[i][r2];
        cout << ans << '\n';
    }
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 2 ms 344 KB Output is correct
5 Correct 4 ms 588 KB Output is correct
6 Correct 9 ms 1368 KB Output is correct
7 Correct 13 ms 1368 KB Output is correct
8 Correct 16 ms 2136 KB Output is correct
9 Correct 27 ms 7256 KB Output is correct
10 Correct 55 ms 18392 KB Output is correct
11 Correct 72 ms 18696 KB Output is correct
12 Correct 97 ms 39124 KB Output is correct
13 Correct 123 ms 36036 KB Output is correct
14 Correct 122 ms 28492 KB Output is correct
15 Correct 183 ms 46580 KB Output is correct

Subtask #2
15.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 2368 ms 71316 KB Output is correct
2 Correct 3640 ms 81616 KB Output is correct
3 Correct 3572 ms 107676 KB Output is correct
4 Runtime error 47 ms 131072 KB Execution killed with signal 9
5 Runtime error 50 ms 131072 KB Execution killed with signal 9
6 Runtime error 48 ms 131072 KB Execution killed with signal 9
7 Runtime error 75 ms 131072 KB Execution killed with signal 9
8 Runtime error 49 ms 131072 KB Execution killed with signal 9
9 Runtime error 59 ms 131072 KB Execution killed with signal 9
10 Runtime error 48 ms 131072 KB Execution killed with signal 9
11 Runtime error 45 ms 131072 KB Execution killed with signal 9
12 Runtime error 47 ms 131072 KB Execution killed with signal 9
13 Runtime error 47 ms 131072 KB Execution killed with signal 9
14 Runtime error 45 ms 131072 KB Execution killed with signal 9
15 Runtime error 46 ms 131072 KB Execution killed with signal 9
16 Runtime error 52 ms 131072 KB Execution killed with signal 9
17 Runtime error 50 ms 131072 KB Execution killed with signal 9