oj.uz

Submission #867746

# Submission time Handle Problem Language Result Execution time Memory
867746 2023-10-29T12:07:59 Z overwatch9 Regions (IOI09_regions) C++17
24 / 100
 8000 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;
int n, r, q;
vector <int> dfs(int s, int p, int r1, int x) {
    vector <int> tp(r+1);
    tp[col[s]] += x;
    for (auto i : adj[s]) {
        if (i == p)
            continue;
        vector <int> res;
        if (col[s] == r1)
            res = dfs(i, s, r1, x+1);
        else
            res = dfs(i, s, r1, x);
        for (int j = 1; j <= r; j++)
            tp[j] += res[j];
    }
    return tp;
}
int main() {
    cin >> n >> r >> q;
    col = vector <int> (n+1);
    adj.resize(n+1);
    ans.resize(n+1);
    cin >> col[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;
    }
    for (int i = 1; i <= r; i++) {
        ans[i] = dfs(1, 1, i, 0);
    }
    while (q--) {
        int r1, r2;
        cin >> r1 >> r2;
        cout << ans[r1][r2] << '\n';
    }
}

Subtask #1
14.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 3 ms 344 KB Output is correct
5 Correct 6 ms 344 KB Output is correct
6 Correct 54 ms 1644 KB Output is correct
7 Correct 44 ms 600 KB Output is correct
8 Correct 99 ms 976 KB Output is correct
9 Correct 2227 ms 8216 KB Output is correct
10 Correct 1400 ms 2440 KB Output is correct
11 Correct 1313 ms 2716 KB Output is correct
12 Execution timed out 8005 ms 11440 KB Time limit exceeded
13 Correct 2020 ms 3140 KB Output is correct
14 Correct 1062 ms 3340 KB Output is correct
15 Correct 4843 ms 49664 KB Output is correct

Subtask #2
10.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 5194 ms 21772 KB Output is correct
2 Correct 3767 ms 9460 KB Output is correct
3 Execution timed out 8093 ms 50816 KB Time limit exceeded
4 Execution timed out 8007 ms 30768 KB Time limit exceeded
5 Runtime error 73 ms 131072 KB Execution killed with signal 9
6 Runtime error 144 ms 131072 KB Execution killed with signal 9
7 Runtime error 352 ms 131072 KB Execution killed with signal 9
8 Runtime error 91 ms 131072 KB Execution killed with signal 9
9 Runtime error 177 ms 131072 KB Execution killed with signal 9
10 Runtime error 135 ms 131072 KB Execution killed with signal 9
11 Runtime error 1121 ms 131072 KB Execution killed with signal 9
12 Runtime error 1158 ms 131072 KB Execution killed with signal 9
13 Runtime error 209 ms 131072 KB Execution killed with signal 9
14 Runtime error 1323 ms 131072 KB Execution killed with signal 9
15 Runtime error 138 ms 131072 KB Execution killed with signal 9
16 Runtime error 139 ms 131072 KB Execution killed with signal 9
17 Runtime error 143 ms 131072 KB Execution killed with signal 9