oj.uz

Submission #686807

# Submission time Handle Problem Language Result Execution time Memory
686807 2023-01-26T00:58:06 Z boyliguanhan Regions (IOI09_regions) C++17
18 / 100
 1291 ms 131072 KB 
#include<bits/stdc++.h>
using namespace std;
vector<int> adj[200100];
int region[200100];
int answers[501][501];
vector<int> regions[25100];
map<int, int> vals[200100];
void merge(map<int, int> &a, map<int, int> b){
    if(a.size()<b.size())
        swap(a, b);
    for(auto i: b)
        a[i.first]+=i.second;
}
void dfs(int n){
    regions[region[n]].push_back(n);
    vals[n][region[n]]=1;
    for(auto i: adj[n]){
        dfs(i);
        merge(vals[n], vals[i]);
    }
}
int main(){
    int n, r, q;
    cin >> n >> r >> q;
    cin >> region[0];
    for(int i = 1; i < n; i++){
        int p;
        cin >> p >> region[i];
        adj[p-1].push_back(i);
    }
    dfs(0);
    if(r<501){
        for(int i = 1; i <= r; i++){
            for(auto j : regions[i]){
                for(auto k: vals[j]){
                    answers[i][k.first]+=k.second;
                }
            }
        }
        while(q--){
            int a, b;
            cin >> a >> b;
            cout << answers[a][b] << endl;
        }
    } else {
        while(q--){
            int a, b, ans = 0;
            cin >> a >> b;
            for(auto i: regions[a])
                if(vals[i].count(b))
                    ans+=vals[i][b];
            cout << ans << endl;
        }
    }
    return 0;
}

Subtask #1
13.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 14928 KB Output is correct
2 Correct 10 ms 14988 KB Output is correct
3 Correct 9 ms 15056 KB Output is correct
4 Correct 14 ms 15056 KB Output is correct
5 Correct 13 ms 15440 KB Output is correct
6 Correct 32 ms 22096 KB Output is correct
7 Correct 33 ms 16592 KB Output is correct
8 Correct 40 ms 18768 KB Output is correct
9 Correct 176 ms 82624 KB Output is correct
10 Correct 114 ms 26732 KB Output is correct
11 Correct 144 ms 48072 KB Output is correct
12 Runtime error 132 ms 131072 KB Execution killed with signal 9
13 Correct 165 ms 23232 KB Output is correct
14 Correct 174 ms 40880 KB Output is correct
15 Runtime error 133 ms 131072 KB Execution killed with signal 9

Subtask #2
5.0 / 85.0

# Verdict Execution time Memory Grader output
1 Runtime error 164 ms 131072 KB Execution killed with signal 9
2 Correct 1291 ms 126388 KB Output is correct
3 Runtime error 159 ms 131072 KB Execution killed with signal 9
4 Runtime error 139 ms 131072 KB Execution killed with signal 9
5 Runtime error 137 ms 131072 KB Execution killed with signal 9
6 Runtime error 142 ms 131072 KB Execution killed with signal 9
7 Runtime error 167 ms 131072 KB Execution killed with signal 9
8 Runtime error 172 ms 131072 KB Execution killed with signal 9
9 Runtime error 200 ms 131072 KB Execution killed with signal 9
10 Runtime error 210 ms 131072 KB Execution killed with signal 9
11 Runtime error 256 ms 131072 KB Execution killed with signal 9
12 Runtime error 227 ms 131072 KB Execution killed with signal 9
13 Runtime error 208 ms 131072 KB Execution killed with signal 9
14 Runtime error 226 ms 131072 KB Execution killed with signal 9
15 Runtime error 217 ms 131072 KB Execution killed with signal 9
16 Runtime error 212 ms 131072 KB Execution killed with signal 9
17 Runtime error 220 ms 131072 KB Execution killed with signal 9