oj.uz

Submission #298970

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

typedef long long ll;

int LIM = 1000;
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 6 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 11 ms 6272 KB Output is correct
6 Correct 22 ms 6400 KB Output is correct
7 Correct 19 ms 6400 KB Output is correct
8 Correct 33 ms 6520 KB Output is correct
9 Correct 51 ms 6912 KB Output is correct
10 Correct 82 ms 7160 KB Output is correct
11 Correct 88 ms 7424 KB Output is correct
12 Correct 80 ms 8064 KB Output is correct
13 Correct 103 ms 7936 KB Output is correct
14 Correct 183 ms 8732 KB Output is correct
15 Correct 212 ms 11384 KB Output is correct

Subtask #2
75.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 884 ms 13292 KB Output is correct
2 Correct 993 ms 12304 KB Output is correct
3 Correct 1333 ms 15508 KB Output is correct
4 Correct 225 ms 8728 KB Output is correct
5 Correct 322 ms 10240 KB Output is correct
6 Correct 713 ms 10232 KB Output is correct
7 Correct 972 ms 11760 KB Output is correct
8 Correct 1055 ms 17000 KB Output is correct
9 Correct 1486 ms 19372 KB Output is correct
10 Correct 2071 ms 23672 KB Output is correct
11 Correct 2320 ms 19960 KB Output is correct
12 Correct 4116 ms 83532 KB Output is correct
13 Correct 4516 ms 83748 KB Output is correct
14 Execution timed out 8048 ms 99140 KB Time limit exceeded
15 Correct 7799 ms 124104 KB Output is correct
16 Correct 6881 ms 128904 KB Output is correct
17 Execution timed out 8023 ms 107804 KB Time limit exceeded