oj.uz

Submission #298972

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

int LIM = 700;
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 8 ms 6400 KB Output is correct
4 Correct 11 ms 6272 KB Output is correct
5 Correct 12 ms 6272 KB Output is correct
6 Correct 14 ms 6400 KB Output is correct
7 Correct 33 ms 6400 KB Output is correct
8 Correct 36 ms 6400 KB Output is correct
9 Correct 50 ms 6912 KB Output is correct
10 Correct 104 ms 7060 KB Output is correct
11 Correct 101 ms 7424 KB Output is correct
12 Correct 175 ms 8064 KB Output is correct
13 Correct 150 ms 7936 KB Output is correct
14 Correct 183 ms 8824 KB Output is correct
15 Correct 246 ms 11444 KB Output is correct

Subtask #2
70.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 914 ms 13172 KB Output is correct
2 Correct 1042 ms 12272 KB Output is correct
3 Correct 1608 ms 15476 KB Output is correct
4 Correct 258 ms 8576 KB Output is correct
5 Correct 343 ms 10332 KB Output is correct
6 Correct 972 ms 10104 KB Output is correct
7 Correct 1014 ms 11640 KB Output is correct
8 Correct 1371 ms 16888 KB Output is correct
9 Correct 2058 ms 19372 KB Output is correct
10 Correct 2088 ms 23544 KB Output is correct
11 Correct 2519 ms 19832 KB Output is correct
12 Correct 4220 ms 83556 KB Output is correct
13 Correct 5196 ms 83712 KB Output is correct
14 Execution timed out 8023 ms 99160 KB Time limit exceeded
15 Execution timed out 8026 ms 124120 KB Time limit exceeded
16 Correct 7378 ms 128932 KB Output is correct
17 Execution timed out 8028 ms 107848 KB Time limit exceeded