Submission #543770

#	Time	Username	Problem	Language	Result	Execution time	Memory
543770		Mazaalai	Regions (IOI09_regions)	C++17	100 / 100	2209 ms	51804 KiB

regions

#include <bits/stdc++.h>

#define ff first
#define ss second
#define pb push_back
#define LINE "------------------------\n"
using namespace std;
using PII = pair <int, int>;
const int N = 2e5 + 5;
const int M = 25e3+5;
const int K = 160;
int k;
int par[N], region[N], regionCnt[M], compress[N];
vector <int> paths[N], in[N], out[N];
int n, m, q, last = 1, Comp = 1;
PII range[N];
void dfs(int pos, int p = 1) {
    in[region[pos]].pb(last++);
    for (auto& el : paths[pos]) 
        dfs(el, pos);
    out[region[pos]].pb(last-1);
}
int dp1[K][N], dp2[K][N];
int up[N], down[N];
void calc1(int a) { // r1, r2 => a == r1;
    for (int i = 1; i <= n; i++) {
        down[i] = down[par[i]]+(region[i]==a);
        dp1[compress[a]][region[i]] += down[i];
    }
}
void calc2(int a) { // r1, r2 => a == r2;
    for (int i = n; i > 0; i--) {
        up[i] = (region[i] == a);
        for (auto& el : paths[i]) up[i] += up[el];
        dp2[compress[a]][region[i]] += up[i];
    }
}
void calc() {
    dfs(1);
    k = sqrt(n);
    for (int i = 1; i <= n; i++) regionCnt[region[i]]++;
    for (int i = 1; i <= m; i++) {
        if (regionCnt[i] >= k) {
            // cout << "HERE: " << i << ' ' << regionCnt[i] << " " << Comp << ' ' << k << "\n";
            compress[i] = Comp++;
            calc1(i);
            calc2(i);
        }
    }
    for (int i = 1; i <= m; i++) {
        in[i].pb(n+5);
        out[i].pb(n+5);
    }
}
int answer(int a, int b) {
    // cout << a << ' ' << regionCnt
    if (regionCnt[a] >= k) return dp1[compress[a]][b];
    if (regionCnt[b] >= k) return dp2[compress[b]][a];
    // cout << "IN " << a << ": "; for (auto el : in[a]) cout << el << ' '; cout << '\n';
    // cout << "OUT " << a << ": "; for (auto el : out[a]) cout << el << ' '; cout << '\n';
    // cout << "IN " << b << ": "; for (auto el : in[b]) cout << el << ' '; cout << '\n';
    int ans = 0;
    {
        int x = 0, y = 0, cur = 0;
        while (x < out[a].size()-1 || y < in[b].size()-1) {
            if (out[a][x] < in[b][y]) {
                ans += cur;
                x++;
            } else {
                cur++;
                y++;
            }
        }

    }
    {
        int x = 0, y = 0, cur = 0;
        while (x < in[a].size()-1 || y < in[b].size()-1) {
            if (in[a][x] < in[b][y]) {
                ans -= cur;
                x++;
            } else {
                cur++;
                y++;
            }
        }

    }
    return ans;
}
signed main() {
    // freopen("0.in", "r", stdin);
    // freopen("0.out", "w", stdout);
    cin >> n >> m >> q;
    cin >> region[1];
    for (int i = 2; i <= n; i++) {
        cin >> par[i] >> region[i];
        paths[par[i]].pb(i);
    }
    calc();
    for (int i = 1; i <= q; i++) {
        int a, b; cin >> a >> b;
        cout << answer(a, b) << endl;
    }
}

Compilation message (stderr)

regions.cpp: In function 'int answer(int, int)':
regions.cpp:65:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |         while (x < out[a].size()-1 || y < in[b].size()-1) {
      |                ~~^~~~~~~~~~~~~~~~~
regions.cpp:65:41: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |         while (x < out[a].size()-1 || y < in[b].size()-1) {
      |                                       ~~^~~~~~~~~~~~~~~~
regions.cpp:78:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |         while (x < in[a].size()-1 || y < in[b].size()-1) {
      |                ~~^~~~~~~~~~~~~~~~
regions.cpp:78:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |         while (x < in[a].size()-1 || y < in[b].size()-1) {
      |                                      ~~^~~~~~~~~~~~~~~~

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