oj.uz

Submission #298945

# Submission time Handle Problem Language Result Execution time Memory
298945 2020-09-14T11:03:11 Z jovan_b Regions (IOI09_regions) C++17
55 / 100
 3607 ms 131076 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];

ll gore[25005][505];
ll 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 4 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 21 ms 6400 KB Output is correct
7 Correct 29 ms 6400 KB Output is correct
8 Correct 35 ms 6400 KB Output is correct
9 Correct 49 ms 6912 KB Output is correct
10 Correct 79 ms 7068 KB Output is correct
11 Correct 103 ms 7424 KB Output is correct
12 Correct 128 ms 8064 KB Output is correct
13 Correct 149 ms 7936 KB Output is correct
14 Correct 178 ms 8824 KB Output is correct
15 Correct 208 ms 11512 KB Output is correct

Subtask #2
40.0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 772 ms 13984 KB Output isn't correct
2 Incorrect 944 ms 13184 KB Output isn't correct
3 Incorrect 1343 ms 16624 KB Output isn't correct
4 Correct 249 ms 8696 KB Output is correct
5 Correct 303 ms 10360 KB Output is correct
6 Correct 671 ms 10232 KB Output is correct
7 Correct 921 ms 11768 KB Output is correct
8 Correct 788 ms 17016 KB Output is correct
9 Correct 1440 ms 19452 KB Output is correct
10 Correct 1980 ms 23544 KB Output is correct
11 Correct 2246 ms 19960 KB Output is correct
12 Runtime error 3525 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
13 Runtime error 3597 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
14 Runtime error 3607 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
15 Runtime error 886 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
16 Runtime error 792 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
17 Runtime error 3375 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)