oj.uz

Submission #298968

# Submission time Handle Problem Language Result Execution time Memory
298968 2020-09-14T11:23:40 Z jovan_b Regions (IOI09_regions) C++17
90 / 100
 8000 ms 128924 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

int LIM = 500;
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;
        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 5 ms 6272 KB Output is correct
3 Correct 6 ms 6272 KB Output is correct
4 Correct 8 ms 6272 KB Output is correct
5 Correct 12 ms 6272 KB Output is correct
6 Correct 20 ms 6400 KB Output is correct
7 Correct 32 ms 6400 KB Output is correct
8 Correct 38 ms 6400 KB Output is correct
9 Correct 53 ms 6912 KB Output is correct
10 Correct 80 ms 7040 KB Output is correct
11 Correct 69 ms 7424 KB Output is correct
12 Correct 133 ms 8064 KB Output is correct
13 Correct 150 ms 7936 KB Output is correct
14 Correct 185 ms 8704 KB Output is correct
15 Correct 206 ms 11392 KB Output is correct

Subtask #2
75.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 849 ms 13192 KB Output is correct
2 Correct 931 ms 12316 KB Output is correct
3 Correct 1485 ms 15476 KB Output is correct
4 Correct 234 ms 8696 KB Output is correct
5 Correct 286 ms 10360 KB Output is correct
6 Correct 679 ms 10232 KB Output is correct
7 Correct 944 ms 11756 KB Output is correct
8 Correct 858 ms 17016 KB Output is correct
9 Correct 1365 ms 19372 KB Output is correct
10 Correct 1911 ms 23544 KB Output is correct
11 Correct 2236 ms 19832 KB Output is correct
12 Correct 4102 ms 83796 KB Output is correct
13 Correct 4526 ms 83940 KB Output is correct
14 Execution timed out 8042 ms 99432 KB Time limit exceeded
15 Correct 7579 ms 124412 KB Output is correct
16 Correct 6797 ms 128924 KB Output is correct
17 Execution timed out 8061 ms 108068 KB Time limit exceeded