제출 #1131174

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1131174		minhnguyent546	Regions (IOI09_regions)	C++17	100 / 100	4570 ms	58516 KiB

regions

/**            
 * author      minhnguyent546
 * created_at  Wed, 2025-01-01 16:52:58
 * problem     https://oj.uz/problem/view/IOI09_regions
 **/           
#include <bits/stdc++.h>
using namespace std;

#ifdef LOCAL
#include "cp/debug.h"
#else
#define debug(...)
#define cerr if (false) cerr
#endif

int n, r, q;
const int N = (int) 2e5 + 3;
const int R = (int) 25e3 + 3;
vector<int> g[N];
int house[N], par[N];
vector<int> vers[R];
int tin[N], tout[N];
int timer = 0;

void dfs(int u) {
    tin[u] = timer++;
    for (int v : g[u]) {
        dfs(v);
    }
    tout[u] = timer - 1;
}

template<typename T>
struct Fenwick {
    int n;
    vector<T> tree;
    Fenwick() {}
    Fenwick(int _n): n(_n), tree(n) {}
    void add(int i, T val) {
        while (i < n) {
            tree[i] += val;
            i |= (i + 1);
        }
    }
    T pref(int i) {
        T res{};
        while (i >= 0) {
            res += tree[i];
            i = (i & (i + 1)) - 1;
        }
        return res;
    }
    T query(int l, int r) { return pref(r) - pref(l - 1); }
};

void read_input() {
    cin >> n >> r >> q;
    cin >> house[0];
    --house[0];
    for (int i = 1; i < n; ++i) {
        int x, h;
        cin >> x >> h;
        --x; --h;
        par[i] = x;
        g[x].emplace_back(i);
        house[i] = h;
    }

    for (int i = 0; i < n; ++i) {
        vers[house[i]].emplace_back(i);
    }
}

namespace sub1 {
bool check() {
    return r <= 500;
}

void solve() {
    dfs(0);
    vector<vector<int>> cnt(r, vector<int>(r));
    Fenwick<int> tree(n);
    for (int r1 = 0; r1 < r; ++r1) {
        for (int r2 = 0; r2 < r; ++r2) {
            if (r2 == r1) continue;
            for (int ver : vers[r2]) {
                tree.add(tin[ver], 1);
            }
            for (int ver : vers[r1]) {
                cnt[r1][r2] += tree.query(tin[ver] + 1, tout[ver]);
            }

            // reset
            for (int ver : vers[r2]) {
                tree.add(tin[ver], -1);
            }
        }
    }
    for (int w = 0; w < q; ++w) {
        int r1, r2;
        cin >> r1 >> r2;
        --r1; --r2;
        cout << cnt[r1][r2] << endl;
    }
}

void solve2() {
    dfs(0);
    vector<vector<int>> cnt(r, vector<int>(r));
    vector<int> pref(n + 3);
    for (int r1 = 0; r1 < r; ++r1) {
        fill(pref.begin(), pref.end(), 0);
        for (int ver : vers[r1]) {
            ++pref[tin[ver] + 1];
            --pref[tout[ver] + 1];
        }
        for (int i = 1; i <= n; ++i) {
            pref[i] += pref[i - 1];
        }

        for (int r2 = 0; r2 < r; ++r2) {
            if (r2 == r1) continue;
            for (int ver : vers[r2]) {
                cnt[r1][r2] += pref[tin[ver]];
            }
        }
    }
    for (int w = 0; w < q; ++w) {
        int r1, r2;
        cin >> r1 >> r2;
        --r1; --r2;
        cout << cnt[r1][r2] << endl;
    }
}
} // namespace sub1

namespace sub2 {
bool check() {
    for (int i = 0; i < r; ++i) {
        if ((int) vers[i].size() > 500) return false;
    }
    return true;
}

void solve() {
    dfs(0);
    Fenwick<int> tree(n);
    for (int w = 0; w < q; ++w) {
        int r1, r2;
        cin >> r1 >> r2;
        --r1; --r2;
        assert(r1 != r2);
        for (int ver : vers[r2]) {
            tree.add(tin[ver], 1);
        }
        int ans = 0;
        for (int ver : vers[r1]) {
            ans += tree.query(tin[ver] + 1, tout[ver]);
        }

        // reset
        for (int ver : vers[r2]) {
            tree.add(tin[ver], -1);
        }

        cout << ans << endl;
    }
}
} // namespace sub2 

namespace sub3 {

#ifdef LOCAL
const int THRESSHOLD = 2;
#else
const int THRESSHOLD =                          450;
#endif

const int NUM_LARGES = 450 + 3;
int cnt_large_large[NUM_LARGES][NUM_LARGES];
int pref_for_small_large[NUM_LARGES][N + 3];
int pref_for_large_small[NUM_LARGES][N + 3];

bool check() {
    return true;
}

void solve() {
    dfs(0);
    vector<int> large_idx(r, -1);
    vector<int> who;
    int num_larges = 0;
    for (int i = 0; i < r; ++i) {
        if ((int) vers[i].size() > THRESSHOLD) {
            large_idx[i] = num_larges++;
            who.emplace_back(i);
        }
    }

    Fenwick<int> tree(n);
    // assert(num_larges <= 400);
    for (int i = 0; i < num_larges; ++i) {
        int r1 = who[i];
        for (int j = 0; j < num_larges; ++j) {
            int r2 = who[j];
            if (r1 == r2) continue;
            for (int ver : vers[r2]) {
                tree.add(tin[ver], 1);
            }
            for (int ver : vers[r1]) {
                cnt_large_large[i][j] += tree.query(tin[ver] + 1, tout[ver]);
            }

            // reset
            for (int ver : vers[r2]) {
                tree.add(tin[ver], -1);
            }
        }
    }

    for (int i = 0; i < num_larges; ++i) {
        for (int v : vers[who[i]]) {
            pref_for_small_large[i][tin[v] + 1]++;
        }
        for (int j = 1; j <= n; ++j) {
            pref_for_small_large[i][j] += pref_for_small_large[i][j - 1];
        }
    }

    for (int i = 0; i < num_larges; ++i) {
        for (int v : vers[who[i]]) {
            pref_for_large_small[i][tin[v] + 1]++;
            pref_for_large_small[i][tout[v] + 1]--;
        }
        for (int j = 1; j <= n; ++j) {
            pref_for_large_small[i][j] += pref_for_large_small[i][j - 1];
        }
    }
    
    for (int w = 0; w < q; ++w) {
        int r1, r2;
        cin >> r1 >> r2;
        --r1; --r2;
        assert(r1 != r2);

        int ans = 0;
        if (large_idx[r1] != -1 && large_idx[r2] != -1) {
            // both r1 and r2 are large
            ans = cnt_large_large[large_idx[r1]][large_idx[r2]];
        } else if (large_idx[r1] != -1) {
            // r1 is large, r2 is small
            for (int ver : vers[r2]) {
                ans += pref_for_large_small[large_idx[r1]][tin[ver]];
            }
        } else if (large_idx[r2] != -1) {
            // r1 is small, r2 is large
            for (int ver : vers[r1]) {
                ans += pref_for_small_large[large_idx[r2]][tout[ver] + 1] - pref_for_small_large[large_idx[r2]][tin[ver] + 1];
            }
        } else {
            // both r1 and r2 are small
            
            for (int ver : vers[r2]) {
                tree.add(tin[ver], 1);
            }

            for (int ver : vers[r1]) {
                ans += tree.query(tin[ver] + 1, tout[ver]);
            }

            // reset
            for (int ver : vers[r2]) {
                tree.add(tin[ver], -1);
            }

        }
        cout << ans << endl;
        
    }
}
} // namespace sub3
int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    cin.exceptions(cin.failbit);
    read_input();

    #ifdef LOCAL
        // sub1::solve2();
        sub3::solve();
        return 0;
    #endif

    if (sub1::check()) {
        sub1::solve2();
        return 0;
    }
    if (sub2::check()) {
        sub2::solve();
        return 0;
    }

    if (sub3::check()) {
        sub3::solve();
        return 0;
    }
    assert(false);
    
    return 0;
}

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