Submission #1037196

#	Time	Username	Problem	Language	Result	Execution time	Memory
1037196		Br3ad	Regions (IOI09_regions)	C++17	20 / 100	4420 ms	131072 KiB

regions

#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 / 15
• Subtask 2: 5 / 85