oj.uz

Submission #867741

# Submission time Handle Problem Language Result Execution time Memory
867741 2023-10-29T11:51:20 Z overwatch9 Regions (IOI09_regions) C++17
13 / 100
 859 ms 131072 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>
using namespace std;
vector <vector <int>> adj;
vector <int> col;
vector <unordered_map <int, int>> freq;
vector <vector <int>> regions;
unordered_map <int, int> dfs(int s, int p) {
    unordered_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 344 KB Output is correct
3 Correct 1 ms 460 KB Output is correct
4 Correct 2 ms 760 KB Output is correct
5 Correct 5 ms 1420 KB Output is correct
6 Correct 17 ms 6512 KB Output is correct
7 Correct 19 ms 2876 KB Output is correct
8 Correct 25 ms 5528 KB Output is correct
9 Correct 112 ms 66752 KB Output is correct
10 Correct 103 ms 19272 KB Output is correct
11 Correct 250 ms 51704 KB Output is correct
12 Runtime error 120 ms 131072 KB Execution killed with signal 9
13 Correct 358 ms 50332 KB Output is correct
14 Correct 859 ms 105172 KB Output is correct
15 Runtime error 130 ms 131072 KB Execution killed with signal 9

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Runtime error 142 ms 131072 KB Execution killed with signal 9
2 Runtime error 301 ms 131072 KB Execution killed with signal 9
3 Runtime error 146 ms 131072 KB Execution killed with signal 9
4 Runtime error 123 ms 131072 KB Execution killed with signal 9
5 Runtime error 133 ms 131072 KB Execution killed with signal 9
6 Runtime error 141 ms 131072 KB Execution killed with signal 9
7 Runtime error 152 ms 131072 KB Execution killed with signal 9
8 Runtime error 160 ms 131072 KB Execution killed with signal 9
9 Runtime error 197 ms 131072 KB Execution killed with signal 9
10 Runtime error 202 ms 131072 KB Execution killed with signal 9
11 Runtime error 214 ms 131072 KB Execution killed with signal 9
12 Runtime error 215 ms 131072 KB Execution killed with signal 9
13 Runtime error 204 ms 131072 KB Execution killed with signal 9
14 Runtime error 209 ms 131072 KB Execution killed with signal 9
15 Runtime error 224 ms 131072 KB Execution killed with signal 9
16 Runtime error 245 ms 131072 KB Execution killed with signal 9
17 Runtime error 204 ms 131072 KB Execution killed with signal 9