oj.uz

Submission #298961

# Submission time Handle Problem Language Result Execution time Memory
298961 2020-09-14T11:15:47 Z jovan_b Regions (IOI09_regions) C++17
55 / 100
 8000 ms 129028 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[region[v]];
        }
        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 5 ms 6272 KB Output is correct
3 Correct 6 ms 6272 KB Output is correct
4 Correct 7 ms 6272 KB Output is correct
5 Correct 11 ms 6272 KB Output is correct
6 Correct 24 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 51 ms 6912 KB Output is correct
10 Correct 70 ms 7040 KB Output is correct
11 Correct 90 ms 7468 KB Output is correct
12 Correct 128 ms 8064 KB Output is correct
13 Correct 155 ms 8056 KB Output is correct
14 Correct 173 ms 8824 KB Output is correct
15 Correct 220 ms 11384 KB Output is correct

Subtask #2
40.0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 818 ms 13188 KB Output isn't correct
2 Incorrect 879 ms 12304 KB Output isn't correct
3 Incorrect 1469 ms 15604 KB Output isn't correct
4 Correct 240 ms 8696 KB Output is correct
5 Correct 330 ms 10328 KB Output is correct
6 Correct 680 ms 10232 KB Output is correct
7 Correct 1016 ms 11640 KB Output is correct
8 Correct 973 ms 16888 KB Output is correct
9 Correct 1485 ms 19496 KB Output is correct
10 Correct 2025 ms 23544 KB Output is correct
11 Correct 2153 ms 19960 KB Output is correct
12 Incorrect 4075 ms 83628 KB Output isn't correct
13 Incorrect 4156 ms 83888 KB Output isn't correct
14 Execution timed out 8026 ms 99180 KB Time limit exceeded
15 Incorrect 7512 ms 124416 KB Output isn't correct
16 Incorrect 6803 ms 129028 KB Output isn't correct
17 Execution timed out 8018 ms 107956 KB Time limit exceeded