oj.uz

Submission #298933

# Submission time Handle Problem Language Result Execution time Memory
298933 2020-09-14T10:52:16 Z jovan_b Regions (IOI09_regions) C++17
55 / 100
 8000 ms 129044 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];

bool is_parent(int a, int b){
    return in[a] <= in[b] && out[b] <= out[a];
}

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);

    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){
            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;
        }
        //cout << "jng";
        int k = svi[a].size();
       // cout << k << endl;
        //for(auto c : svi[a]) cout << c.first << " " << c.second << endl;
        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++;
                //cout << j << " i " << c << endl;
                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 5 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 12 ms 6272 KB Output is correct
5 Correct 10 ms 6272 KB Output is correct
6 Correct 19 ms 6400 KB Output is correct
7 Correct 31 ms 6400 KB Output is correct
8 Correct 31 ms 6400 KB Output is correct
9 Correct 48 ms 7032 KB Output is correct
10 Correct 60 ms 7160 KB Output is correct
11 Correct 93 ms 7424 KB Output is correct
12 Correct 135 ms 8184 KB Output is correct
13 Correct 98 ms 7936 KB Output is correct
14 Correct 163 ms 8832 KB Output is correct
15 Correct 166 ms 11440 KB Output is correct

Subtask #2
40.0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 664 ms 13292 KB Output isn't correct
2 Incorrect 1155 ms 12312 KB Output isn't correct
3 Incorrect 1464 ms 15508 KB Output isn't correct
4 Correct 266 ms 8696 KB Output is correct
5 Correct 412 ms 10240 KB Output is correct
6 Correct 724 ms 10232 KB Output is correct
7 Correct 954 ms 11768 KB Output is correct
8 Correct 740 ms 17016 KB Output is correct
9 Correct 1160 ms 19476 KB Output is correct
10 Correct 1833 ms 23544 KB Output is correct
11 Correct 2477 ms 19960 KB Output is correct
12 Incorrect 3917 ms 83652 KB Output isn't correct
13 Incorrect 4461 ms 83676 KB Output isn't correct
14 Execution timed out 8044 ms 99236 KB Time limit exceeded
15 Incorrect 7841 ms 124128 KB Output isn't correct
16 Incorrect 6526 ms 129044 KB Output isn't correct
17 Execution timed out 8028 ms 107904 KB Time limit exceeded