oj.uz

Submission #298948

# Submission time Handle Problem Language Result Execution time Memory
298948 2020-09-14T11:08:56 Z jovan_b Regions (IOI09_regions) C++17
0 / 100
 3736 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);
    return 0;
    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
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 6272 KB Unexpected end of file - int32 expected
2 Incorrect 4 ms 6272 KB Unexpected end of file - int32 expected
3 Incorrect 4 ms 6272 KB Unexpected end of file - int32 expected
4 Incorrect 4 ms 6272 KB Unexpected end of file - int32 expected
5 Incorrect 5 ms 6272 KB Unexpected end of file - int32 expected
6 Incorrect 5 ms 6400 KB Unexpected end of file - int32 expected
7 Incorrect 5 ms 6400 KB Unexpected end of file - int32 expected
8 Incorrect 5 ms 6400 KB Unexpected end of file - int32 expected
9 Incorrect 8 ms 6912 KB Unexpected end of file - int32 expected
10 Incorrect 9 ms 7040 KB Unexpected end of file - int32 expected
11 Incorrect 10 ms 7424 KB Unexpected end of file - int32 expected
12 Incorrect 13 ms 8064 KB Unexpected end of file - int32 expected
13 Incorrect 18 ms 7936 KB Unexpected end of file - int32 expected
14 Incorrect 17 ms 8704 KB Unexpected end of file - int32 expected
15 Incorrect 21 ms 11392 KB Unexpected end of file - int32 expected

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 45 ms 13940 KB Unexpected end of file - int32 expected
2 Incorrect 51 ms 13168 KB Unexpected end of file - int32 expected
3 Incorrect 59 ms 16500 KB Unexpected end of file - int32 expected
4 Incorrect 20 ms 8568 KB Unexpected end of file - int32 expected
5 Incorrect 19 ms 10232 KB Unexpected end of file - int32 expected
6 Incorrect 32 ms 10112 KB Unexpected end of file - int32 expected
7 Incorrect 42 ms 11640 KB Unexpected end of file - int32 expected
8 Incorrect 52 ms 16888 KB Unexpected end of file - int32 expected
9 Incorrect 84 ms 19320 KB Unexpected end of file - int32 expected
10 Incorrect 84 ms 23592 KB Unexpected end of file - int32 expected
11 Incorrect 116 ms 19832 KB Unexpected end of file - int32 expected
12 Runtime error 3589 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
13 Runtime error 3615 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
14 Runtime error 3736 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
15 Runtime error 939 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
16 Runtime error 848 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
17 Runtime error 3449 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)