Submission #1037275

#	Time	Username	Problem	Language	Result	Execution time	Memory
1037275		Br3ad	Regions (IOI09_regions)	C++17	55 / 100	8090 ms	87668 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
    BIT bit(2*n);
    get_euler(1);
 
    while(q--){
        int r1, r2;
        cin >> r1 >> r2;
 
        if(precal[r1] != -1){
            cout << pre[precal[r1]][r2] << endl;
        }else {
            vector<pair<int, int>> v;
            for(int i : reg_member[r2]) v.PB(MP(tin[i], 0));
            for(int i : reg_member[r1]){
                v.PB(MP(tin[i], 1));
                v.PB(MP(tout[i], -1));
            }

            sort(v.begin(), v.end());

            int ans = 0, cur = 0;
            for(auto [_, num] : v){
                cur += num;
                if(!num) ans += cur;
            }
 
            cout << ans << endl;
        }
    }
}

• Subtask 1: 15 / 15
• Subtask 2: 40 / 85