oj.uz

Submission #298971

# Submission time Handle Problem Language Result Execution time Memory
298971 2020-09-14T11:26:11 Z jovan_b Regions (IOI09_regions) C++17
85 / 100
 8000 ms 131076 KB 
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#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 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 8 ms 6272 KB Output is correct
5 Correct 11 ms 6272 KB Output is correct
6 Correct 38 ms 6400 KB Output is correct
7 Correct 38 ms 6400 KB Output is correct
8 Correct 56 ms 6400 KB Output is correct
9 Correct 77 ms 7168 KB Output is correct
10 Correct 124 ms 7040 KB Output is correct
11 Correct 164 ms 7424 KB Output is correct
12 Correct 147 ms 8320 KB Output is correct
13 Correct 171 ms 7936 KB Output is correct
14 Correct 203 ms 8696 KB Output is correct
15 Correct 335 ms 13304 KB Output is correct

Subtask #2
70.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1313 ms 13888 KB Output is correct
2 Correct 988 ms 12524 KB Output is correct
3 Correct 2036 ms 17136 KB Output is correct
4 Correct 247 ms 8696 KB Output is correct
5 Correct 323 ms 11520 KB Output is correct
6 Correct 692 ms 10436 KB Output is correct
7 Correct 1169 ms 11988 KB Output is correct
8 Correct 1254 ms 20312 KB Output is correct
9 Correct 1559 ms 20240 KB Output is correct
10 Correct 2164 ms 27768 KB Output is correct
11 Correct 2612 ms 20040 KB Output is correct
12 Correct 3707 ms 83632 KB Output is correct
13 Correct 4365 ms 84672 KB Output is correct
14 Execution timed out 8051 ms 99484 KB Time limit exceeded
15 Correct 7344 ms 127724 KB Output is correct
16 Runtime error 4384 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
17 Execution timed out 8054 ms 115772 KB Time limit exceeded