oj.uz

Submission #298977

# Submission time Handle Problem Language Result Execution time Memory
298977 2020-09-14T11:31:51 Z jovan_b Regions (IOI09_regions) C++17
90 / 100
 8000 ms 129060 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 4 ms 6272 KB Output is correct
2 Correct 4 ms 6272 KB Output is correct
3 Correct 6 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 21 ms 6400 KB Output is correct
7 Correct 25 ms 6400 KB Output is correct
8 Correct 35 ms 6400 KB Output is correct
9 Correct 30 ms 6912 KB Output is correct
10 Correct 81 ms 7160 KB Output is correct
11 Correct 108 ms 7544 KB Output is correct
12 Correct 122 ms 8064 KB Output is correct
13 Correct 140 ms 8056 KB Output is correct
14 Correct 182 ms 8704 KB Output is correct
15 Correct 213 ms 11392 KB Output is correct

Subtask #2
75.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 739 ms 13184 KB Output is correct
2 Correct 966 ms 12316 KB Output is correct
3 Correct 1585 ms 15508 KB Output is correct
4 Correct 257 ms 8568 KB Output is correct
5 Correct 329 ms 10360 KB Output is correct
6 Correct 664 ms 10176 KB Output is correct
7 Correct 786 ms 11752 KB Output is correct
8 Correct 835 ms 16992 KB Output is correct
9 Correct 1424 ms 19368 KB Output is correct
10 Correct 1730 ms 23672 KB Output is correct
11 Correct 2287 ms 19832 KB Output is correct
12 Correct 4195 ms 83752 KB Output is correct
13 Correct 4331 ms 83840 KB Output is correct
14 Execution timed out 8044 ms 99592 KB Time limit exceeded
15 Correct 7296 ms 124572 KB Output is correct
16 Correct 6552 ms 129060 KB Output is correct
17 Execution timed out 8013 ms 108160 KB Time limit exceeded