Submission #391530

#	Time	Username	Problem	Language	Result	Execution time	Memory
391530		MeGustaElArroz23	Regions (IOI09_regions)	C++14	40 / 100	3842 ms	131076 KiB

regions

#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 / 15
• Subtask 2: 25 / 85