oj.uz

Submission #391530

# Submission time Handle Problem Language Result Execution time Memory
391530 2021-04-19T08:51:17 Z MeGustaElArroz23 Regions (IOI09_regions) C++14
40 / 100
 3842 ms 131076 KB 
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> pii;

int main(){
    int n,r,q;
    cin >> n >> r >> q;
    vvi hijos(n+1);
    vector<short> regiones(n+1);
    int a;
    cin >> a;
    regiones[1]=a;
    for (int i=2;i<n+1;i++){
        int a,b;
        cin >> a >> b;
        regiones[i]=b;
        hijos[a].push_back(i);
    }
    vvi sol(r+1,vi(r+1,0));
    for (short i=1;i<r+1;i++){
        queue<pii> cola;
        cola.push(pii{1,0});
        while (cola.size()){
            pii a=cola.front();
            cola.pop();
            sol[i][regiones[a.first]]+=a.second;
            if (regiones[a.first]==i) a.second++;
            for (int x:hijos[a.first]) cola.push(pii{x,a.second});
        }
    }
    while (q--){
        int a,b;
        cin >> a >> b;
        cout << sol[a][b] << endl;
    }
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 4 ms 200 KB Output is correct
4 Correct 6 ms 200 KB Output is correct
5 Correct 8 ms 328 KB Output is correct
6 Correct 30 ms 584 KB Output is correct
7 Correct 32 ms 456 KB Output is correct
8 Correct 52 ms 456 KB Output is correct
9 Correct 62 ms 936 KB Output is correct
10 Correct 161 ms 1480 KB Output is correct
11 Correct 182 ms 1408 KB Output is correct
12 Correct 257 ms 2248 KB Output is correct
13 Correct 356 ms 1776 KB Output is correct
14 Correct 300 ms 1992 KB Output is correct
15 Correct 368 ms 2716 KB Output is correct

Subtask #2
25.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1121 ms 4608 KB Output is correct
2 Correct 1133 ms 4184 KB Output is correct
3 Correct 1638 ms 5664 KB Output is correct
4 Correct 2739 ms 64596 KB Output is correct
5 Correct 3842 ms 100464 KB Output is correct
6 Runtime error 93 ms 131076 KB Execution killed with signal 9
7 Runtime error 104 ms 131076 KB Execution killed with signal 9
8 Runtime error 128 ms 131076 KB Execution killed with signal 9
9 Runtime error 154 ms 131076 KB Execution killed with signal 9
10 Runtime error 172 ms 131076 KB Execution killed with signal 9
11 Runtime error 189 ms 131076 KB Execution killed with signal 9
12 Runtime error 178 ms 131076 KB Execution killed with signal 9
13 Runtime error 181 ms 131076 KB Execution killed with signal 9
14 Runtime error 186 ms 131076 KB Execution killed with signal 9
15 Runtime error 189 ms 131076 KB Execution killed with signal 9
16 Runtime error 184 ms 131076 KB Execution killed with signal 9
17 Runtime error 187 ms 131076 KB Execution killed with signal 9