Submission #899912

#	Time	Username	Problem	Language	Result	Execution time	Memory
899912		ninjamayank	Regions (IOI09_regions)	C++17	45 / 100	3529 ms	131072 KiB

regions

#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#define input(x) for(auto &a:x)cin>>a
#define print(x) for(auto &a:x){cout<<a<<' ';}cout<<nline
#define ppcl(x) __builtin_popcountll(x)
#define ppc(x) __builtin_popcount(x)
#define all(x) x.begin(), x.end()
#define ll long long int
#define ld long double
#define pb push_back
#define nline "\n"
#define INF LLONG_MAX
#define NINF LLONG_MIN
#define pii pair<int,int> 
#define fr first
#define sc second 
using namespace std;
using namespace __gnu_pbds;
#define precision(x) fixed << setprecision(x)
#define uid(a, b) uniform_int_distribution<int>(a, b)(rng)
#define ordered_set tree<ll, null_type,less<ll>, rb_tree_tag,tree_order_statistics_node_update>
const ll mod = 1e9 + 7;
const int N = 200001;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

ll n,r,q;
vector<ll> reg(N), id(N), in(N), out(N);
vector<vector<ll>> g(N);
vector<vector<ll>> res(25010), region(25010);
vector<vector<ll>> dp(500,vector<ll>(25010));
ll cnt = 0,timer = 0, counter = 0;

void dfs(ll u, ll p){
    in[u] = timer++;
    res[reg[u]].pb(in[u]);
    region[reg[u]].pb(u);
    for(auto &child : g[u]){
        if(child == p) continue;
        dfs(child,u);
    }
    out[u] = timer++;
}

void sq_dfs(ll u, ll p, ll col){
    if(reg[u] == col){
        cnt++;
    }else{
        dp[id[col]][reg[u]] += cnt;
    }
    for(auto &child : g[u]){
        if(child == p) continue;
        sq_dfs(child,p,col);
    }
    if(reg[u] == col){
        cnt--;
    }
}

void ninjamayank(){
    cin >> n >> r >> q;
    cin >> reg[0];
    for(ll i = 1;i < n;i++){
        ll x;
        cin >> x >> reg[i];
        --x;
        g[x].pb(i);
        g[i].pb(x);
    }
    dfs(0,-1);
    for(ll i = 1;i <= r;i++){
        ll sz = res[i].size();
        if(sz > 500){
            id[i] = counter++;
            sq_dfs(0,-1,i);
        }
    }
    while(q--){
        ll r1,r2;
        cin >> r1 >> r2;
        ll sz = res[r1].size();
        ll ans = 0;
        if(sz < 500){
            for(ll i = 0;i < sz;i++){
                ans += lower_bound(all(res[r2]),out[region[r1][i]]) - lower_bound(all(res[r2]),in[region[r1][i]]);
            }
        }else{
            ans = dp[id[r1]][r2];
        }
        cout << ans << endl;
    }
}
int main(){
    // #ifndef ONLINE_JUDGE
    //     //for getting input from input1.txt
    //     freopen("input1.txt", "r", stdin);
    //     //for getting output from output1.txt
    //     freopen("output1.txt", "w", stdout);
    // #endif
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); // remove in problems with online query
    int testcase = 1;
    // cin >> testcase;
    int gtc = 1;
    while(testcase--){
        //cout << "Case #" << gtc << ": ";
        ninjamayank();
        gtc++;
    }
}

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