oj.uz

Submission #765320

# Submission time Handle Problem Language Result Execution time Memory
765320 2023-06-24T10:43:31 Z keta_tsimakuridze Regions (IOI09_regions) C++14
55 / 100
 1239 ms 131072 KB 
#include<bits/stdc++.h>
#define f first
#define s second
#define int long long
#define pii pair<int,int>
using namespace std;
const int N = 2e5 + 5, M = 25e3 + 5, mod = 1e9 + 7, B = 2e3; // !
int t, a[N], id[M], cur, cnt[M], CN2[N][105], CN1[M][105],timer;
vector<pair<int,int>> reg[M];
vector<int> V[N];
void dfs(int u) {
    ++timer;
    reg[a[u]].push_back({timer, 1});
    for(int i = 0; i < V[u].size(); i++) {
        int v = V[u][i];
        dfs(v);
        for(int j = 1; j <= cur; j++) {
            CN2[u][j] += CN2[v][j];
        }
    }
    ++CN2[u][id[a[u]]];
    for(int j = 1; j <= cur; j++) {
        CN1[a[u]][j] += CN2[u][j];
    }
    reg[a[u]].push_back({timer + 1, 0});
}
void dfs2(int u) {
    ++cnt[id[a[u]]];
    for(int j = 1; j <= cur; j++) {
        CN2[a[u]][j] += cnt[j];
    }
    for(int i = 0; i < V[u].size(); i++) dfs2(V[u][i]);
    --cnt[id[a[u]]];
}
main(){
    int n, r, q;
    cin >> n >> r >> q;
    for(int i = 1; i <= n; i++) {
        if(i >= 2) {
            int k; cin >> k;
            V[k].push_back(i);
        }
        cin >> a[i];
        ++cnt[a[i]];
    }
    cur = 0;
    for(int i = 1; i <= r; i++) {
        if(cnt[i] >= B) {
            id[i] = ++cur;
        }
        cnt[i] = 0;
    }
    dfs(1);
    for(int i = 1; i <= n; i++) for(int j = 1; j <= cur; j++) CN2[i][j] = 0;
    dfs2(1);
    while(q--) {
        int u, v;
        cin >> u >> v;
        if(id[u]) {
            cout << CN2[v][id[u]] << endl;
        } else if(id[v]) {
            cout << CN1[u][id[v]] << endl;
        } else {
            int l = -1;
            int cn = 0, ans = 0;
            for(int i = 0; i < reg[u].size(); i++) {
                while(l + 1 < (int)reg[v].size() && reg[v][l + 1].f < reg[u][i].f) {
                    ++l;
                    cn += reg[v][l].s;
                }
                ans += cn * (reg[u][i].s ? -1 : 1);
            }
            cout << ans << endl;
        }
    }
 }

Compilation message

regions.cpp: In function 'void dfs(long long int)':
regions.cpp:14:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   14 |     for(int i = 0; i < V[u].size(); i++) {
      |                    ~~^~~~~~~~~~~~~
regions.cpp: In function 'void dfs2(long long int)':
regions.cpp:32:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |     for(int i = 0; i < V[u].size(); i++) dfs2(V[u][i]);
      |                    ~~^~~~~~~~~~~~~
regions.cpp: At global scope:
regions.cpp:35:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   35 | main(){
      | ^~~~
regions.cpp: In function 'int main()':
regions.cpp:66:30: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |             for(int i = 0; i < reg[u].size(); i++) {
      |                            ~~^~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5584 KB Output is correct
2 Correct 2 ms 5584 KB Output is correct
3 Correct 5 ms 5696 KB Output is correct
4 Correct 6 ms 5712 KB Output is correct
5 Correct 8 ms 5968 KB Output is correct
6 Correct 16 ms 6352 KB Output is correct
7 Correct 29 ms 6992 KB Output is correct
8 Correct 21 ms 7376 KB Output is correct
9 Correct 54 ms 10704 KB Output is correct
10 Correct 68 ms 14672 KB Output is correct
11 Correct 113 ms 19304 KB Output is correct
12 Correct 131 ms 24368 KB Output is correct
13 Correct 136 ms 27324 KB Output is correct
14 Correct 155 ms 33168 KB Output is correct
15 Correct 223 ms 47208 KB Output is correct

Subtask #2
40.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 847 ms 75120 KB Output is correct
2 Correct 786 ms 77496 KB Output is correct
3 Correct 1239 ms 91200 KB Output is correct
4 Correct 261 ms 33112 KB Output is correct
5 Correct 218 ms 42276 KB Output is correct
6 Correct 731 ms 52884 KB Output is correct
7 Correct 984 ms 69312 KB Output is correct
8 Correct 897 ms 104248 KB Output is correct
9 Runtime error 135 ms 131072 KB Execution killed with signal 9
10 Runtime error 124 ms 131072 KB Execution killed with signal 9
11 Runtime error 142 ms 131072 KB Execution killed with signal 9
12 Runtime error 135 ms 131072 KB Execution killed with signal 9
13 Runtime error 140 ms 131072 KB Execution killed with signal 9
14 Runtime error 143 ms 131072 KB Execution killed with signal 9
15 Runtime error 151 ms 131072 KB Execution killed with signal 9
16 Runtime error 169 ms 131072 KB Execution killed with signal 9
17 Runtime error 133 ms 131072 KB Execution killed with signal 9