oj.uz

Submission #867740

# Submission time Handle Problem Language Result Execution time Memory
867740 2023-10-29T11:50:15 Z overwatch9 Regions (IOI09_regions) C++17
13 / 100
 876 ms 131072 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
using namespace std;
vector <vector <int>> adj;
vector <int> col;
vector <map <int, int>> freq;
vector <vector <int>> regions;
map <int, int> dfs(int s, int p) {
    map <int, int> tp;
    tp[col[s]] = 1;
    for (auto i : adj[s]) {
        if (i == p)
            continue;
        auto res = dfs(i, s);
        if (tp.size() < res.size())
            swap(res, tp);
        for (auto j : res)
            tp[j.first] += j.second;
    }
    freq[s] = tp;
    return tp;
}
int main() {
    int n, r, q;
    cin >> n >> r >> q;
    col = vector <int> (n+1);
    adj.resize(n+1);
    regions.resize(r+1);
    freq.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[c].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 << endl;
    }
}

Subtask #1
13.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 432 KB Output is correct
3 Correct 1 ms 456 KB Output is correct
4 Correct 2 ms 636 KB Output is correct
5 Correct 5 ms 1500 KB Output is correct
6 Correct 17 ms 7792 KB Output is correct
7 Correct 26 ms 3340 KB Output is correct
8 Correct 28 ms 5588 KB Output is correct
9 Correct 141 ms 69260 KB Output is correct
10 Correct 140 ms 20472 KB Output is correct
11 Correct 377 ms 55008 KB Output is correct
12 Runtime error 118 ms 131072 KB Execution killed with signal 9
13 Correct 486 ms 53860 KB Output is correct
14 Correct 876 ms 109576 KB Output is correct
15 Runtime error 118 ms 131072 KB Execution killed with signal 9

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Runtime error 140 ms 131072 KB Execution killed with signal 9
2 Runtime error 273 ms 131072 KB Execution killed with signal 9
3 Runtime error 138 ms 131072 KB Execution killed with signal 9
4 Runtime error 125 ms 131072 KB Execution killed with signal 9
5 Runtime error 125 ms 131072 KB Execution killed with signal 9
6 Runtime error 135 ms 131072 KB Execution killed with signal 9
7 Runtime error 143 ms 131072 KB Execution killed with signal 9
8 Runtime error 152 ms 131072 KB Execution killed with signal 9
9 Runtime error 174 ms 131072 KB Execution killed with signal 9
10 Runtime error 193 ms 131072 KB Execution killed with signal 9
11 Runtime error 217 ms 131072 KB Execution killed with signal 9
12 Runtime error 204 ms 131072 KB Execution killed with signal 9
13 Runtime error 192 ms 131072 KB Execution killed with signal 9
14 Runtime error 202 ms 131072 KB Execution killed with signal 9
15 Runtime error 200 ms 131072 KB Execution killed with signal 9
16 Runtime error 190 ms 131072 KB Execution killed with signal 9
17 Runtime error 200 ms 131072 KB Execution killed with signal 9