oj.uz

Submission #765306

# Submission time Handle Problem Language Result Execution time Memory
765306 2023-06-24T10:36:04 Z keta_tsimakuridze Regions (IOI09_regions) C++14
35 / 100
 1063 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 = 2000; // !
int t, a[N], id[M], cur, cnt[M], CN2[105][M], CN1[M][105], dp[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});
    ++cnt[id[a[u]]];
    for(int j = 1; j <= cur; j++) {
        CN2[j][u] += cnt[j];
    }
    for(int i = 0; i < V[u].size(); i++) {
        int v = V[u][i];
        dfs(v);
        for(int j = 1; j <= cur; j++) {
            dp[u][j] += dp[v][j];
        }
    }
    --cnt[id[a[u]]];
    ++dp[u][id[a[u]]];
    for(int j = 1; j <= cur; j++) {
        CN1[u][j] += dp[u][j];
    }
    reg[a[u]].push_back({timer + 1, 0});
}
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]];
    }
//    cout << "+" << endl;
    cur = 0;
    for(int i = 1; i <= r; i++) {
        if(cnt[i] >= B) {
            id[i] = ++cur;
//            val[cur] = i;
        }
        cnt[i] = 0;
    }
    dfs(1);
    while(q--) {
        int u, v;
        cin >> u >> v;
        if(id[u]) {
            cout << CN2[id[u]][v] << endl;
        } else if(id[v]) {
            cout << CN2[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:18: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]
   18 |     for(int i = 0; i < V[u].size(); i++) {
      |                    ~~^~~~~~~~~~~~~
regions.cpp: At global scope:
regions.cpp:32:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   32 | main(){
      | ^~~~
regions.cpp: In function 'int main()':
regions.cpp:63: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]
   63 |             for(int i = 0; i < reg[u].size(); i++) {
      |                            ~~^~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5584 KB Output is correct
2 Correct 3 ms 5584 KB Output is correct
3 Correct 5 ms 5584 KB Output is correct
4 Correct 6 ms 5712 KB Output is correct
5 Correct 6 ms 5968 KB Output is correct
6 Correct 15 ms 6352 KB Output is correct
7 Correct 34 ms 6872 KB Output is correct
8 Correct 43 ms 7424 KB Output is correct
9 Correct 48 ms 10832 KB Output is correct
10 Correct 93 ms 14672 KB Output is correct
11 Correct 95 ms 19280 KB Output is correct
12 Correct 119 ms 24368 KB Output is correct
13 Correct 118 ms 27336 KB Output is correct
14 Correct 155 ms 33172 KB Output is correct
15 Correct 174 ms 47828 KB Output is correct

Subtask #2
20.0 / 85.0

# Verdict Execution time Memory Grader output
1 Runtime error 106 ms 113172 KB Execution killed with signal 11
2 Runtime error 109 ms 95852 KB Execution killed with signal 11
3 Runtime error 52 ms 28716 KB Execution killed with signal 11
4 Correct 273 ms 33140 KB Output is correct
5 Correct 268 ms 42696 KB Output is correct
6 Correct 689 ms 52892 KB Output is correct
7 Correct 1063 ms 69440 KB Output is correct
8 Runtime error 106 ms 103116 KB Execution killed with signal 11
9 Runtime error 130 ms 50024 KB Execution killed with signal 11
10 Runtime error 136 ms 52928 KB Execution killed with signal 11
11 Runtime error 151 ms 95100 KB Execution killed with signal 11
12 Runtime error 209 ms 131072 KB Execution killed with signal 11
13 Runtime error 161 ms 107048 KB Execution killed with signal 11
14 Runtime error 217 ms 131072 KB Execution killed with signal 11
15 Runtime error 117 ms 45372 KB Execution killed with signal 11
16 Runtime error 166 ms 92812 KB Execution killed with signal 11
17 Runtime error 142 ms 78080 KB Execution killed with signal 11