oj.uz

Submission #1037196

# Submission time Handle Problem Language Result Execution time Memory
1037196 2024-07-28T10:24:33 Z Br3ad Regions (IOI09_regions) C++17
20 / 100
 4420 ms 131072 KB 
#include <iostream>
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <functional>
#include <numeric>
#include <cstring>
#include <string>
#include <cmath>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <map>

using namespace std;
#define ll long long
#define ull unsigned long long
#define f first
#define s second
#define PF push_front
#define PB push_back
#define MP make_pair
#define max(a, b) ((a > b)? a : b)
#define min(a, b) ((a < b)? a : b)
#define max3(a, b, c) max(max(a, b), c)
#define min3(a, b, c) min(min(a, b), c)

const int N = 2e5 + 5;
const int M = 1e9 + 7; 
const int inf = 0x3f3f3f3f;
const ll int INF = 1e18;

struct BIT{
    int sz;
    vector<int> tree;

    BIT(int n) : sz(n+1), tree(n+1, 0) {};

    void add(int pos, int val){
        for(; pos < sz; pos += pos&-pos) tree[pos] += val;
    }

    int query(int pos){
        int ans = 0;
        for(; pos >= 1; pos -= pos&-pos) ans += tree[pos];
        return ans;
    }
};

vector<vector<int>> adj(N, vector<int>()), pre;
vector<int> reg(N), tin(N), tout(N);

void pre_dfs(int par_reg, int par_cnt, int cur, vector<int> &pre_temp){
    if(par_reg != reg[cur]) pre_temp[reg[cur]] += par_cnt;
    for(int child : adj[cur]){
        pre_dfs(par_reg, par_cnt + (par_reg == reg[child]), child, pre_temp);
    }
}

int timer = 1;
void get_euler(int cur){
    tin[cur] = timer++;
    for(int child : adj[cur]) get_euler(child);
    tout[cur] = timer++;
}

int main(){
    
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    
    // ifstream cin();
    // ofstream cout();
    
    int n, r, q;
    cin >> n >> r >> q;
    
    cin >> reg[1];
    for(int i = 2; i <= n; i++){
        int par;
        cin >> par >> reg[i];
        adj[par].PB(i);
    }
    
    // Precalculate
    vector<vector<int>> reg_member(r + 1, vector<int>());
    for(int i = 1; i <= n; i++){
        reg_member[reg[i]].PB(i);
    }

    int thres = sqrt(n);
    vector<int> precal(r + 1, -1);
    for(int i = 1; i <= r; i++){
        if((int)reg_member[i].size() > thres){
            vector<int> pre_temp(n+1, 0);
            pre_dfs(i, (reg[1] == i), 1, pre_temp);
            pre.PB(pre_temp);
            precal[i] = (int)pre.size() - 1;
        }
    }

    // Euler tour
    get_euler(1);

    vector<BIT> bit_cache;
    vector<int> reg_cache(r+1, -1);

    while(q--){
        int r1, r2;
        cin >> r1 >> r2;

        if(precal[r1] != -1){
            cout << pre[precal[r1]][r2] << endl;
        }else {
            // Get BIT
            BIT cur_bit(0);
            if(reg_cache[r1] != -1){
                cur_bit = bit_cache[reg_cache[r1]];
            }else {
                cur_bit = BIT(2*n);
                for(int i : reg_member[r1]){
                    cur_bit.add(tin[i], 1);
                    cur_bit.add(tout[i], -1);
                }
                reg_cache[r1] = (int)bit_cache.size();
                bit_cache.PB(cur_bit);
            }

            // Query
            int ans = 0;
            for(int mem : reg_member[r2]){
                ans += cur_bit.query(tin[mem]);
            }

            cout << ans << endl;
        }
    }
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7512 KB Output is correct
2 Correct 2 ms 7512 KB Output is correct
3 Correct 3 ms 7524 KB Output is correct
4 Correct 4 ms 7556 KB Output is correct
5 Correct 5 ms 7512 KB Output is correct
6 Correct 12 ms 9048 KB Output is correct
7 Correct 15 ms 9128 KB Output is correct
8 Correct 24 ms 10768 KB Output is correct
9 Correct 37 ms 19544 KB Output is correct
10 Correct 88 ms 41104 KB Output is correct
11 Correct 129 ms 39928 KB Output is correct
12 Correct 223 ms 79168 KB Output is correct
13 Correct 269 ms 72084 KB Output is correct
14 Correct 375 ms 55392 KB Output is correct
15 Correct 562 ms 86260 KB Output is correct

Subtask #2
5.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 4420 ms 121204 KB Output is correct
2 Runtime error 628 ms 131072 KB Execution killed with signal 9
3 Runtime error 100 ms 131072 KB Execution killed with signal 9
4 Runtime error 81 ms 131072 KB Execution killed with signal 9
5 Runtime error 68 ms 131072 KB Execution killed with signal 9
6 Runtime error 130 ms 131072 KB Execution killed with signal 9
7 Runtime error 174 ms 131072 KB Execution killed with signal 9
8 Runtime error 153 ms 131072 KB Execution killed with signal 9
9 Runtime error 87 ms 131072 KB Execution killed with signal 9
10 Runtime error 200 ms 131072 KB Execution killed with signal 9
11 Runtime error 87 ms 131072 KB Execution killed with signal 9
12 Runtime error 107 ms 131072 KB Execution killed with signal 9
13 Runtime error 107 ms 131072 KB Execution killed with signal 9
14 Runtime error 208 ms 131072 KB Execution killed with signal 9
15 Runtime error 89 ms 131072 KB Execution killed with signal 9
16 Runtime error 88 ms 131072 KB Execution killed with signal 9
17 Runtime error 116 ms 131072 KB Execution killed with signal 9