oj.uz

Submission #765309

# Submission time Handle Problem Language Result Execution time Memory
765309 2023-06-24T10:36:51 Z keta_tsimakuridze Regions (IOI09_regions) C++14
40 / 100
 933 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[N][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 3 ms 5584 KB Output is correct
2 Correct 2 ms 5584 KB Output is correct
3 Correct 4 ms 5584 KB Output is correct
4 Correct 5 ms 5712 KB Output is correct
5 Correct 10 ms 5968 KB Output is correct
6 Correct 19 ms 6352 KB Output is correct
7 Correct 19 ms 6992 KB Output is correct
8 Correct 37 ms 7376 KB Output is correct
9 Correct 43 ms 10832 KB Output is correct
10 Correct 65 ms 14696 KB Output is correct
11 Correct 112 ms 19288 KB Output is correct
12 Correct 108 ms 24400 KB Output is correct
13 Correct 127 ms 27356 KB Output is correct
14 Correct 167 ms 33172 KB Output is correct
15 Correct 220 ms 47708 KB Output is correct

Subtask #2
25.0 / 85.0

# Verdict Execution time Memory Grader output
1 Runtime error 114 ms 122188 KB Execution killed with signal 11
2 Runtime error 113 ms 109316 KB Execution killed with signal 11
3 Runtime error 54 ms 28740 KB Execution killed with signal 11
4 Correct 211 ms 33212 KB Output is correct
5 Correct 366 ms 42660 KB Output is correct
6 Correct 780 ms 52936 KB Output is correct
7 Correct 933 ms 69448 KB Output is correct
8 Correct 911 ms 105204 KB Output is correct
9 Runtime error 124 ms 131072 KB Execution killed with signal 9
10 Runtime error 126 ms 131072 KB Execution killed with signal 9
11 Runtime error 146 ms 131072 KB Execution killed with signal 9
12 Runtime error 219 ms 131072 KB Execution killed with signal 11
13 Runtime error 161 ms 112712 KB Execution killed with signal 11
14 Runtime error 277 ms 131072 KB Execution killed with signal 11
15 Runtime error 173 ms 45352 KB Execution killed with signal 11
16 Runtime error 145 ms 92880 KB Execution killed with signal 11
17 Runtime error 182 ms 78168 KB Execution killed with signal 11