Submission #1001111

#	Time	Username	Problem	Language	Result	Execution time	Memory
1001111		kh0i	Regions (IOI09_regions)	C++17	100 / 100	2935 ms	57780 KiB

regions

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

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...)
#endif

using ll = long long;
using pii = pair<int, int>;

#define F first
#define S second
#define sz(x) (int)((x).size())
#define all(x) (x).begin(), (x).end()

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll get_rand(ll l, ll r) {
    assert(l <= r);
    return uniform_int_distribution<ll> (l, r)(rng);
}

const int N = 2e5 + 3;
const int R = 25003;
const int B = 500;

int n, r, q, h[N], id[N], d[N * 2];
vector<int> g[N], dak[N], big;
int tin[N], tout[N], et[N * 2], timer;

int ansb1[N / B + 2][R], ansb2[N / B + 2][R];
vector<pii> e[N], sus;

void dfs(int u, int pre = -1){
    tin[u] = ++timer;
    et[timer] = u;
    dak[h[u]].push_back(u);
    e[h[u]].push_back({tin[u], 1});
    sus.push_back({tin[u], 1});

    for(int v : g[u])
        if(v != pre)
            dfs(v, u);

    tout[u] = ++timer;
    et[timer] = u;
    e[h[u]].push_back({tout[u], -1});
    sus.push_back({tout[u], -1});
}

void solve(){
    cin >> n >> r >> q;
    cin >> h[1];
    for(int i = 2; i <= n; ++i){
        int p;
        cin >> p >> h[i];
        g[p].push_back(i);
    }
    dfs(1);
    memset(id, -1, sizeof(id));
    for(int i = 1; i <= r; ++i){
        sort(all(e[i]));
        if(sz(dak[i]) >= B){
            id[i] = sz(big);
            big.push_back(i);
        }
    }

    sort(all(sus));

    // precalc
    // big - ?
    for(int r1 : big){
        ll cnt = 0;
        for(auto [x, y] : sus){
            if(h[et[x]] == r1)
                cnt += y;
            else{
                if(y == -1)
                    continue;
                ansb1[id[r1]][h[et[x]]] += cnt;
            }
        }
    }

    // ? - big
    for(int r1 : big){
        for(auto [x, y] : e[r1])
            if(y != -1)
                ++d[x];
        for(int i = 1; i <= timer; ++i)
            d[i] += d[i - 1];

        for(int r2 = 1; r2 <= r; ++r2){
            if(r1 == r2)
                continue;
            for(int u : dak[r2])
                ansb2[id[r1]][r2] += d[tout[u]] - d[tin[u] - 1];
        }

        for(int i = 1; i <= timer; ++i)
            d[i] = 0;
    }

    while(q--){
        int r1, r2;
        cin >> r1 >> r2;
        if(id[r1] != -1)
            cout << ansb1[id[r1]][r2] << endl;
        else if(id[r2] != -1)
            cout << ansb2[id[r2]][r1] << endl;
        else{
            int res = 0;
            vector<pii> x(sz(e[r1]) + sz(e[r2]));
            merge(all(e[r1]), all(e[r2]), x.begin());
            //debug(r1, r2, x);
            int cur = 0;
            for(auto [x, y] : x){
                if(h[et[x]] == r2)
                    res += (y == -1 ? 0 : cur);
                else
                    cur += y;
            }

            cout << res << endl;
        }
    }
}

int32_t main() {
    cin.tie(nullptr)->sync_with_stdio(0);
    #define task "troll"
    if(fopen(task".inp", "r")){
        freopen(task".inp", "r", stdin);
        freopen(task".out", "w", stdout);
    }
    int test = 1;
//    cin >> test;
    for(int i = 1; i <= test; ++i){
//        cout << "Case #" << i << ": ";
        solve();
    }
    #ifdef LOCAL
        cerr << "\n[Time]: " << 1000.0 * clock() / CLOCKS_PER_SEC << " ms.\n";
    #endif
    return 0;
}

Compilation message (stderr)

regions.cpp: In function 'int32_t main()':
regions.cpp:135:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  135 |         freopen(task".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
regions.cpp:136:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  136 |         freopen(task".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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