제출 #898945

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
898945		Amirreza_Fakhri	Regions (IOI09_regions)	C++17	100 / 100	3928 ms	95160 KiB

regions

// In the name of the God 
#include <bits/stdc++.h>
#define ll long long
// #define int long long
#define pb push_back
#define F first
#define S second
#define mp make_pair
#define pii pair <int, int>
#define smin(x, y) (x) = min((x), (y))
#define smax(x, y) (x) = max((x), (y))
#define all(x) (x).begin(), (x).end()
using namespace std;
 
const int inf = 1e9+7;
const int mod = 998244353;
const int maxn = 2e5+5, maxr = 25e3+5, sq = 300, sq_ = 667+2;
 
int n, q, t = 0, cur = 0, re[maxn], id[maxr], cnt[sq_], res[sq_][maxr], in[maxn], out[maxn];
vector <int> adj[maxn], oc[maxr], amir[maxr];

void dfs(int v = 0) {
    in[v] = t++; amir[re[v]].pb(in[v]);
    if (oc[re[v]].size() >= sq) cnt[id[re[v]]]++;
    for (int i = 0; i < sq_; i++) res[i][re[v]] += cnt[i];
    for (int u : adj[v]) dfs(u);
    if (oc[re[v]].size() >= sq) cnt[id[re[v]]]--;
    out[v] = t;
}

int32_t main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> q >> q;
    cin >> re[0]; re[0]--;
    oc[re[0]].pb(0);
    for (int i = 1; i < n; i++) {
        int p; cin >> p >> re[i]; re[i]--;
        adj[--p].pb(i);
        oc[re[i]].pb(i);
    }
    for (int i = 0; i < maxr; i++) {
        if (oc[i].size() >= sq) id[i] = cur++;
    }
    dfs();
    for (int i = 0; i < maxr; i++) sort(all(amir[i]));
    while (q--) {
        int r1, r2; cin >> r1 >> r2; r1--, r2--;
        if (oc[r1].size() >= sq) cout << res[id[r1]][r2];
        else {
            int ans = 0;
            for (int v : oc[r1]) {
                int l = lower_bound(all(amir[r2]), in[v])-amir[r2].begin();
                int r = upper_bound(all(amir[r2]), out[v]-1)-amir[r2].begin();
                ans += r-l;
            }
            cout << ans;
        }
        cout << endl;
    }
    return 0;
}

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