oj.uz

Submission #298974

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

int LIM = 2000;
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 9 ms 6176 KB Output is correct
4 Correct 8 ms 6272 KB Output is correct
5 Correct 11 ms 6272 KB Output is correct
6 Correct 21 ms 6400 KB Output is correct
7 Correct 37 ms 6400 KB Output is correct
8 Correct 37 ms 6400 KB Output is correct
9 Correct 76 ms 6912 KB Output is correct
10 Correct 68 ms 7040 KB Output is correct
11 Correct 113 ms 7468 KB Output is correct
12 Correct 126 ms 8064 KB Output is correct
13 Correct 131 ms 7936 KB Output is correct
14 Correct 176 ms 8704 KB Output is correct
15 Correct 205 ms 11392 KB Output is correct

Subtask #2
80.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 867 ms 13168 KB Output is correct
2 Correct 1006 ms 12272 KB Output is correct
3 Correct 1642 ms 15504 KB Output is correct
4 Correct 237 ms 8576 KB Output is correct
5 Correct 326 ms 10240 KB Output is correct
6 Correct 711 ms 10232 KB Output is correct
7 Correct 933 ms 11640 KB Output is correct
8 Correct 930 ms 17000 KB Output is correct
9 Correct 1669 ms 19364 KB Output is correct
10 Correct 2136 ms 23544 KB Output is correct
11 Correct 2656 ms 19908 KB Output is correct
12 Correct 4067 ms 83516 KB Output is correct
13 Correct 4670 ms 83728 KB Output is correct
14 Correct 6723 ms 99096 KB Output is correct
15 Execution timed out 8026 ms 124072 KB Time limit exceeded
16 Correct 6820 ms 128892 KB Output is correct
17 Correct 6980 ms 107868 KB Output is correct