oj.uz

Submission #298939

# Submission time Handle Problem Language Result Execution time Memory
298939 2020-09-14T10:54:42 Z jovan_b Regions (IOI09_regions) C++17
55 / 100
 2632 ms 23672 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){
            return 0;
            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 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 19 ms 6400 KB Output is correct
7 Correct 33 ms 6400 KB Output is correct
8 Correct 23 ms 6400 KB Output is correct
9 Correct 52 ms 6912 KB Output is correct
10 Correct 80 ms 7160 KB Output is correct
11 Correct 104 ms 7424 KB Output is correct
12 Correct 131 ms 8064 KB Output is correct
13 Correct 163 ms 8056 KB Output is correct
14 Correct 116 ms 8704 KB Output is correct
15 Correct 210 ms 11392 KB Output is correct

Subtask #2
40.0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 23 ms 9088 KB Unexpected end of file - int32 expected
2 Incorrect 26 ms 8448 KB Unexpected end of file - int32 expected
3 Incorrect 28 ms 9720 KB Unexpected end of file - int32 expected
4 Correct 248 ms 8704 KB Output is correct
5 Correct 296 ms 10240 KB Output is correct
6 Correct 644 ms 10176 KB Output is correct
7 Correct 879 ms 11760 KB Output is correct
8 Correct 729 ms 16996 KB Output is correct
9 Correct 1446 ms 19448 KB Output is correct
10 Correct 2071 ms 23672 KB Output is correct
11 Correct 2632 ms 19832 KB Output is correct
12 Incorrect 60 ms 13560 KB Unexpected end of file - int32 expected
13 Incorrect 56 ms 13048 KB Unexpected end of file - int32 expected
14 Incorrect 63 ms 13048 KB Unexpected end of file - int32 expected
15 Incorrect 58 ms 14076 KB Unexpected end of file - int32 expected
16 Incorrect 63 ms 14200 KB Unexpected end of file - int32 expected
17 Incorrect 57 ms 14072 KB Unexpected end of file - int32 expected