oj.uz

Submission #765297

# Submission time Handle Problem Language Result Execution time Memory
765297 2023-06-24T10:31:27 Z keta_tsimakuridze Regions (IOI09_regions) C++14
35 / 100
 931 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 = 1000; // !
int t, a[N], id[N], cur, cnt[N], CN2[205][N], CN1[N][205], dp[N][205], 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 9680 KB Output is correct
2 Correct 5 ms 9708 KB Output is correct
3 Correct 6 ms 9808 KB Output is correct
4 Correct 9 ms 9872 KB Output is correct
5 Correct 7 ms 10576 KB Output is correct
6 Correct 15 ms 11088 KB Output is correct
7 Correct 28 ms 12240 KB Output is correct
8 Correct 30 ms 13136 KB Output is correct
9 Correct 44 ms 18800 KB Output is correct
10 Correct 81 ms 26576 KB Output is correct
11 Correct 103 ms 35152 KB Output is correct
12 Correct 133 ms 44112 KB Output is correct
13 Correct 126 ms 50168 KB Output is correct
14 Correct 113 ms 60760 KB Output is correct
15 Correct 219 ms 82632 KB Output is correct

Subtask #2
20.0 / 85.0

# Verdict Execution time Memory Grader output
1 Runtime error 80 ms 131072 KB Execution killed with signal 9
2 Runtime error 82 ms 131072 KB Execution killed with signal 9
3 Runtime error 76 ms 131072 KB Execution killed with signal 9
4 Correct 279 ms 60704 KB Output is correct
5 Correct 365 ms 75272 KB Output is correct
6 Correct 685 ms 97628 KB Output is correct
7 Correct 931 ms 128312 KB Output is correct
8 Runtime error 89 ms 131072 KB Execution killed with signal 9
9 Runtime error 128 ms 131072 KB Execution killed with signal 9
10 Runtime error 150 ms 131072 KB Execution killed with signal 9
11 Runtime error 150 ms 131072 KB Execution killed with signal 9
12 Runtime error 124 ms 131072 KB Execution killed with signal 9
13 Runtime error 133 ms 131072 KB Execution killed with signal 9
14 Runtime error 134 ms 131072 KB Execution killed with signal 9
15 Runtime error 138 ms 131072 KB Execution killed with signal 9
16 Runtime error 140 ms 131072 KB Execution killed with signal 9
17 Runtime error 151 ms 131072 KB Execution killed with signal 9