oj.uz

Submission #298979

# Submission time Handle Problem Language Result Execution time Memory
298979 2020-09-14T11:33:16 Z jovan_b Regions (IOI09_regions) C++17
100 / 100
 7800 ms 128936 KB 
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;

int LIM = 3000;
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[i];
        }
        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;
        int 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 5 ms 6272 KB Output is correct
3 Correct 7 ms 6272 KB Output is correct
4 Correct 9 ms 6272 KB Output is correct
5 Correct 12 ms 6272 KB Output is correct
6 Correct 22 ms 6400 KB Output is correct
7 Correct 31 ms 6400 KB Output is correct
8 Correct 35 ms 6400 KB Output is correct
9 Correct 31 ms 6912 KB Output is correct
10 Correct 80 ms 7160 KB Output is correct
11 Correct 105 ms 7424 KB Output is correct
12 Correct 127 ms 8064 KB Output is correct
13 Correct 143 ms 7936 KB Output is correct
14 Correct 147 ms 8732 KB Output is correct
15 Correct 217 ms 11512 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 865 ms 13176 KB Output is correct
2 Correct 961 ms 12336 KB Output is correct
3 Correct 1547 ms 15524 KB Output is correct
4 Correct 244 ms 8696 KB Output is correct
5 Correct 333 ms 10336 KB Output is correct
6 Correct 691 ms 10180 KB Output is correct
7 Correct 936 ms 11756 KB Output is correct
8 Correct 765 ms 17016 KB Output is correct
9 Correct 1425 ms 19372 KB Output is correct
10 Correct 2162 ms 23544 KB Output is correct
11 Correct 2392 ms 19908 KB Output is correct
12 Correct 3840 ms 83540 KB Output is correct
13 Correct 4287 ms 83728 KB Output is correct
14 Correct 6628 ms 99088 KB Output is correct
15 Correct 7800 ms 124100 KB Output is correct
16 Correct 6796 ms 128936 KB Output is correct
17 Correct 7061 ms 107876 KB Output is correct