Submission #898960

#	Time	Username	Problem	Language	Result	Execution time	Memory
898960		a_l_i_r_e_z_a	Regions (IOI09_regions)	C++14	100 / 100	3148 ms	33848 KiB

regions

// In the name of Allah
// Hope is last to die
// Khodaya khodet komak kon
// Let's go

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define pb push_back
#define S second
#define F first
#define mp make_pair
#define smax(x, y) (x) = max((x), (y))
#define smin(x, y) (x) = min((x), (y))
#define all(x) (x).begin(), (x).end()
#define sz(x) ((int)(x).size())

const int maxn = 2e5 + 10, msq = 330 + 10, maxr = 25000 + 10;
const int inf = 1e9 + 7;
int n, q, R, T, cnt, col, cnoma, sq, dp[msq][maxr], noma[maxn];
int in[maxn], out[maxn], reg[maxn];
vector<int> adj[maxn], region[maxr], alo[maxn];

void dfs(int v = 1){
    in[v] = T++;
    region[reg[v]].pb(v);
    alo[reg[v]].pb(in[v]);
    for(auto u: adj[v]) dfs(u);
    out[v] = T;
}

void dfs_dp(int v, int col){
    if(reg[v] == col) cnt++;
    else dp[noma[col]][reg[v]] += cnt;
    for(auto u: adj[v]) dfs_dp(u, col);
    if(reg[v] == col) cnt--;
}

int32_t main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    cin >> n >> R >> q;
    sq = 600;
    cin >> reg[1];
    for(int i = 2; i <= n; i++){
        int p; cin >> p >> reg[i];
        adj[p].pb(i);
    }
    dfs();
    for(int i = 1; i <= R; i++){
        if(sz(region[i]) >= sq){
            noma[i] = ++cnoma;
            dfs_dp(1, i);
        }
    }
    while(q--){
        int reg1, reg2; cin >> reg1 >> reg2;
        if(sz(region[reg1]) <= sq){
            int ans = 0;
            for(auto v: region[reg1]){
                int l = lower_bound(all(alo[reg2]), in[v]) - alo[reg2].begin();
                int r = upper_bound(all(alo[reg2]), out[v] - 1) - alo[reg2].begin();
                ans += r - l;
            }
            cout << ans << endl;
        }
        else cout << dp[noma[reg1]][reg2] << endl;
    }

    return 0;
}

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