oj.uz

Submission #765299

# Submission time Handle Problem Language Result Execution time Memory
765299 2023-06-24T10:33:39 Z keta_tsimakuridze Regions (IOI09_regions) C++14
40 / 100
 967 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, mod = 1e9 + 7, B = 2000; // !
int t, a[N], id[N], cur, cnt[N], CN2[105][N], CN1[N][105], dp[N][105], timer;
vector<pair<int,int>> reg[N];
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 6 ms 9748 KB Output is correct
2 Correct 4 ms 9680 KB Output is correct
3 Correct 9 ms 9680 KB Output is correct
4 Correct 8 ms 9808 KB Output is correct
5 Correct 12 ms 10164 KB Output is correct
6 Correct 27 ms 10448 KB Output is correct
7 Correct 32 ms 11088 KB Output is correct
8 Correct 35 ms 11472 KB Output is correct
9 Correct 56 ms 14980 KB Output is correct
10 Correct 53 ms 18768 KB Output is correct
11 Correct 93 ms 23400 KB Output is correct
12 Correct 117 ms 28528 KB Output is correct
13 Correct 123 ms 31408 KB Output is correct
14 Correct 153 ms 37200 KB Output is correct
15 Correct 225 ms 51952 KB Output is correct

Subtask #2
25.0 / 85.0

# Verdict Execution time Memory Grader output
1 Runtime error 92 ms 131072 KB Execution killed with signal 9
2 Runtime error 80 ms 131072 KB Execution killed with signal 9
3 Runtime error 85 ms 131072 KB Execution killed with signal 9
4 Correct 256 ms 37244 KB Output is correct
5 Correct 311 ms 46776 KB Output is correct
6 Correct 784 ms 57008 KB Output is correct
7 Correct 967 ms 73480 KB Output is correct
8 Correct 857 ms 109380 KB Output is correct
9 Runtime error 139 ms 131072 KB Execution killed with signal 9
10 Runtime error 128 ms 131072 KB Execution killed with signal 9
11 Runtime error 189 ms 131072 KB Execution killed with signal 9
12 Runtime error 138 ms 131072 KB Execution killed with signal 9
13 Runtime error 137 ms 131072 KB Execution killed with signal 9
14 Runtime error 148 ms 131072 KB Execution killed with signal 9
15 Runtime error 143 ms 131072 KB Execution killed with signal 9
16 Runtime error 152 ms 131072 KB Execution killed with signal 9
17 Runtime error 147 ms 131072 KB Execution killed with signal 9