oj.uz

Submission #765337

# Submission time Handle Problem Language Result Execution time Memory
765337 2023-06-24T11:01:09 Z keta_tsimakuridze Regions (IOI09_regions) C++14
100 / 100
 4638 ms 59552 KB 
#include<bits/stdc++.h>
#define f first
#define s second
#define ll long long
#define pii pair<int,int>
using namespace std;
const int N = 2e5 + 5, M = 25e3 + 5, mod = 1e9 + 7, B = 400; // !
int t, a[N], timer, id[M], cur, cnt[M], CN[M], in[N], out[N];
ll CN2[505][M];
vector<int> reg[M];
vector<int> V[N];
set<pii> s[N];
void dfs2(int u) {
    in[u] = ++timer;
    ++cnt[id[a[u]]];
    s[a[u]].insert({in[u], (int)s[a[u]].size()});
    reg[a[u]].push_back(u);
    for(int j = 1; j <= cur; j++) {
        CN2[j][a[u]] += cnt[j];
    }
    for(int i = 0; i < V[u].size(); i++) dfs2(V[u][i]);
    --cnt[id[a[u]]];
    out[u] = timer;
}
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;
    }
    for(int i = 1; i <= r; i++) cnt[i] = 0, s[i].insert({0, 0});
    dfs2(1);
    while(q--) {
        int u, v;
        cin >> u >> v;
        if(id[u]) {
            cout << CN2[id[u]][v] << endl;
        } else {
            ll ans = 0;
            for(int j = 0; j < reg[u].size(); j++) {
                ans += (*--s[v].upper_bound({out[reg[u][j]] + 1, 0})).s - (*--s[v].upper_bound({in[reg[u][j]], 0})).s;
            }
            cout << ans << endl;
        }
    }
 }

Compilation message

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

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 14912 KB Output is correct
2 Correct 6 ms 14928 KB Output is correct
3 Correct 8 ms 14928 KB Output is correct
4 Correct 12 ms 14928 KB Output is correct
5 Correct 13 ms 15056 KB Output is correct
6 Correct 25 ms 15144 KB Output is correct
7 Correct 26 ms 15056 KB Output is correct
8 Correct 28 ms 15184 KB Output is correct
9 Correct 32 ms 15824 KB Output is correct
10 Correct 90 ms 15964 KB Output is correct
11 Correct 136 ms 16420 KB Output is correct
12 Correct 97 ms 17188 KB Output is correct
13 Correct 180 ms 16952 KB Output is correct
14 Correct 280 ms 17712 KB Output is correct
15 Correct 298 ms 21892 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1955 ms 23296 KB Output is correct
2 Correct 2429 ms 21892 KB Output is correct
3 Correct 3475 ms 26208 KB Output is correct
4 Correct 255 ms 17996 KB Output is correct
5 Correct 364 ms 20708 KB Output is correct
6 Correct 399 ms 24036 KB Output is correct
7 Correct 1454 ms 24660 KB Output is correct
8 Correct 1073 ms 38772 KB Output is correct
9 Correct 2672 ms 31416 KB Output is correct
10 Correct 3267 ms 59552 KB Output is correct
11 Correct 4638 ms 33376 KB Output is correct
12 Correct 1488 ms 34376 KB Output is correct
13 Correct 2153 ms 35100 KB Output is correct
14 Correct 2572 ms 38488 KB Output is correct
15 Correct 3773 ms 41688 KB Output is correct
16 Correct 3707 ms 50840 KB Output is correct
17 Correct 3113 ms 52016 KB Output is correct