oj.uz

Submission #298947

# Submission time Handle Problem Language Result Execution time Memory
298947 2020-09-14T11:06:42 Z jovan_b Regions (IOI09_regions) C++17
55 / 100
 3609 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;
    }
    if(ccomp > 500){
        cout << 1/0;
        return 0;
    }
    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;
}

Compilation message

regions.cpp: In function 'int main()':
regions.cpp:71:18: warning: division by zero [-Wdiv-by-zero]
   71 |         cout << 1/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 5 ms 6272 KB Output is correct
4 Correct 7 ms 6272 KB Output is correct
5 Correct 8 ms 6272 KB Output is correct
6 Correct 25 ms 6400 KB Output is correct
7 Correct 31 ms 6400 KB Output is correct
8 Correct 41 ms 6400 KB Output is correct
9 Correct 46 ms 6912 KB Output is correct
10 Correct 81 ms 7160 KB Output is correct
11 Correct 86 ms 7672 KB Output is correct
12 Correct 122 ms 8064 KB Output is correct
13 Correct 121 ms 8056 KB Output is correct
14 Correct 151 ms 8740 KB Output is correct
15 Correct 204 ms 11512 KB Output is correct

Subtask #2
40.0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 816 ms 13984 KB Output isn't correct
2 Incorrect 792 ms 13296 KB Output isn't correct
3 Incorrect 1392 ms 16536 KB Output isn't correct
4 Correct 251 ms 8568 KB Output is correct
5 Correct 453 ms 10340 KB Output is correct
6 Correct 619 ms 10108 KB Output is correct
7 Correct 1000 ms 11768 KB Output is correct
8 Correct 881 ms 17000 KB Output is correct
9 Correct 1124 ms 19448 KB Output is correct
10 Correct 2149 ms 23544 KB Output is correct
11 Correct 2401 ms 19908 KB Output is correct
12 Runtime error 3536 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
13 Runtime error 3609 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
14 Runtime error 3597 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
15 Runtime error 877 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
16 Runtime error 822 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
17 Runtime error 3343 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)