oj.uz

Submission #298964

# Submission time Handle Problem Language Result Execution time Memory
298964 2020-09-14T11:17:53 Z jovan_b Regions (IOI09_regions) C++17
100 / 100
 4347 ms 30092 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

int LIM = 50000000;
int in[200005];
int out[200005];
int region[200005];
int parent[200005];
int cnt[200005];
vector <int> graf[200005];

int gore[25005][505];
int dole[25005][505];

int sada[25005];
int rev[25005];
int compress[25005];
int ccomp;

int r;

int tajm;

vector <pair <int, int>> svi[25005];
vector <int> ins[25005];

void dfs(int v){

    in[v] = ++tajm;
    sada[region[v]]++;
    if(compress[region[v]]){
        for(int i=1; i<=r; i++){
            dole[i][compress[region[v]]] += sada[region[v]];
        }
        dole[region[v]][compress[region[v]]]--;
        gore[region[v]][compress[region[v]]]--;
    }
    for(int i=1; i<=ccomp; i++){
        gore[region[v]][i] += sada[rev[i]];
    }
    for(auto c : graf[v]){
        dfs(c);
    }
    sada[region[v]]--;
    out[v] = tajm;
    svi[region[v]].push_back({in[v], 1});
    svi[region[v]].push_back({out[v]+1, -1});
    ins[region[v]].push_back(in[v]);
}

int main(){
    ios_base::sync_with_stdio(false), cin.tie(0);

    int n, q;
    cin >> n >> r >> q;
    cin >> region[1];
    cnt[region[1]]++;
    for(int i=2; i<=n; i++){
        cin >> parent[i] >> region[i];
        cnt[region[i]]++;
        graf[parent[i]].push_back(i);
    }
    for(int i=1; i<=r; i++){
        if(cnt[i] <= LIM) continue;
        compress[i] = ++ccomp;
        rev[ccomp] = i;
    }
    dfs(1);
    for(int i=1; i<=r; i++) sort(svi[i].begin(), svi[i].end());
    for(int i=1; i<=r; i++) sort(ins[i].begin(), ins[i].end());
    while(q--){
        int a, b;
        cin >> a >> b;
        if(cnt[a] > LIM){
            cout << gore[b][compress[a]] << endl;
            continue;
        }
        if(cnt[b] > LIM){
            cout << dole[a][compress[b]] << endl;
            continue;
        }
        int k = svi[a].size();
        int j = -1;
        int tren = 0;
        ll res = 0;
        for(auto c : ins[b]){
            while(j < k-1 && c >= svi[a][j+1].first){
                j++;
                tren += svi[a][j].second;
            }
            res += tren;
        }
        cout << res << endl;
    }

    return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 6272 KB Output is correct
2 Correct 4 ms 6272 KB Output is correct
3 Correct 5 ms 6272 KB Output is correct
4 Correct 8 ms 6272 KB Output is correct
5 Correct 9 ms 6272 KB Output is correct
6 Correct 24 ms 6400 KB Output is correct
7 Correct 25 ms 6400 KB Output is correct
8 Correct 31 ms 6400 KB Output is correct
9 Correct 45 ms 6912 KB Output is correct
10 Correct 70 ms 7040 KB Output is correct
11 Correct 110 ms 7424 KB Output is correct
12 Correct 128 ms 8112 KB Output is correct
13 Correct 146 ms 7936 KB Output is correct
14 Correct 190 ms 8704 KB Output is correct
15 Correct 222 ms 11384 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 2606 ms 12308 KB Output is correct
2 Correct 3993 ms 11428 KB Output is correct
3 Correct 3836 ms 14468 KB Output is correct
4 Correct 304 ms 8764 KB Output is correct
5 Correct 497 ms 10340 KB Output is correct
6 Correct 893 ms 10180 KB Output is correct
7 Correct 881 ms 11760 KB Output is correct
8 Correct 1078 ms 16992 KB Output is correct
9 Correct 1520 ms 19320 KB Output is correct
10 Correct 2325 ms 23672 KB Output is correct
11 Correct 2496 ms 19904 KB Output is correct
12 Correct 1967 ms 20720 KB Output is correct
13 Correct 2148 ms 20892 KB Output is correct
14 Correct 2877 ms 20840 KB Output is correct
15 Correct 3616 ms 25200 KB Output is correct
16 Correct 3497 ms 30092 KB Output is correct
17 Correct 4347 ms 29352 KB Output is correct