oj.uz

Submission #120983

# Submission time Handle Problem Language Result Execution time Memory
120983 2019-06-25T20:59:30 Z Osama_Alkhodairy Regions (IOI09_regions) C++17
100 / 100
 4018 ms 31184 KB 
#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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 6784 KB Output is correct
2 Correct 7 ms 6784 KB Output is correct
3 Correct 9 ms 6784 KB Output is correct
4 Correct 11 ms 6784 KB Output is correct
5 Correct 12 ms 6784 KB Output is correct
6 Correct 29 ms 6872 KB Output is correct
7 Correct 39 ms 7040 KB Output is correct
8 Correct 44 ms 6912 KB Output is correct
9 Correct 66 ms 7444 KB Output is correct
10 Correct 50 ms 7780 KB Output is correct
11 Correct 91 ms 8092 KB Output is correct
12 Correct 141 ms 8748 KB Output is correct
13 Correct 158 ms 8856 KB Output is correct
14 Correct 153 ms 9600 KB Output is correct
15 Correct 160 ms 11680 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 2271 ms 13444 KB Output is correct
2 Correct 3720 ms 12752 KB Output is correct
3 Correct 4018 ms 15304 KB Output is correct
4 Correct 206 ms 9592 KB Output is correct
5 Correct 317 ms 11052 KB Output is correct
6 Correct 678 ms 11384 KB Output is correct
7 Correct 938 ms 13352 KB Output is correct
8 Correct 968 ms 18472 KB Output is correct
9 Correct 1292 ms 22264 KB Output is correct
10 Correct 1741 ms 26796 KB Output is correct
11 Correct 1992 ms 23208 KB Output is correct
12 Correct 1596 ms 23420 KB Output is correct
13 Correct 1882 ms 23624 KB Output is correct
14 Correct 2831 ms 24184 KB Output is correct
15 Correct 3170 ms 28616 KB Output is correct
16 Correct 3629 ms 31184 KB Output is correct
17 Correct 3664 ms 30508 KB Output is correct