Submission #120983

#	Time	Username	Problem	Language	Result	Execution time	Memory
120983		Osama_Alkhodairy	Regions (IOI09_regions)	C++17	100 / 100	4018 ms	31184 KiB

regions

#include <bits/stdc++.h>
using namespace std;
#define finish(x) return cout << x << endl, 0
#define ll long long

const int N = 200001;
const int R = 25001;

struct interval{
    int l, r, val;
};

int n, r, q, reg[N], in[N], out[N];
vector <int> v[N], p[R], ins[R];
vector <interval> invs[R];
int t;

void dfsz(int node, int pnode){
    in[node] = ++t;
    p[reg[node]].push_back(node);
    ins[reg[node]].push_back(in[node]);
    for(auto &i : v[node]){
        if(i == pnode) continue;
        dfsz(i, node);
    }
    out[node] = t;
}
int calc(vector <interval> &x, vector <int> &y){
    int ret = 0;
    int ind = 0;
    for(auto &i : y){
        while(i > x[ind].r) ind++;
        ret += x[ind].val;
    }
    return ret;
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> r >> q >> reg[1];
    for(int i = 2 ; i <= n ; i++){
        int p;
        cin >> p >> reg[i];
        v[p].push_back(i);
    }
    dfsz(1, 0);
    for(int i = 1 ; i <= r ; i++){
        sort(p[i].begin(), p[i].end());
        sort(ins[i].begin(), ins[i].end());
        vector <pair <int, int> > cur;
        for(auto &j : p[i]){
            cur.push_back({in[j], 1});
            cur.push_back({out[j] + 1, -1});
        }
        sort(cur.begin(), cur.end());
        if(cur.size() == 0 || cur[0].first != 1) cur.insert(cur.begin(), {1, 0});
        if(cur.back().first != n + 1) cur.push_back({n + 1, 0});
        int sum = cur[0].second;
        for(int j = 1 ; j < (int)cur.size() ; j++){
            if(cur[j].first != cur[j - 1].first){
                invs[i].push_back({cur[j - 1].first, cur[j].first - 1, sum});
            }
            sum += cur[j].second;
        }
    }
    while(q--){
        int r1, r2;
        cin >> r1 >> r2;
        cout << calc(invs[r1], ins[r2]) << endl;
    }
}

• Subtask 1: 15 / 15
• Subtask 2: 85 / 85