Submission #850301

#	Time	Username	Problem	Language	Result	Execution time	Memory
850301		Shreyan_Paliwal	Regions (IOI09_regions)	C++17	100 / 100	1792 ms	67472 KiB

regions

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;

#define int long long

const int INF = LLONG_MAX / 2 - INT_MAX;

const int maxn = 200005;
const int maxr = 25005;
const int sqrtn = 450;
const int sqrtr = 160;

int n, r, q;
vector<int> adj[maxn];
int re[maxn];

int cnt = 0;
vector<int> sts[maxr], ens[maxr];
int s[maxr], prec[sqrtr][maxr], prec2[maxr][sqrtr], cnt2 = 0;

void dfs(int nd, int par) {
    sts[re[nd]].push_back(cnt++);

    for (auto i : adj[nd])
        if (i != par)
            dfs(i, nd);

    ens[re[nd]].push_back(cnt);
}

int curreg;
int dfs2(int nd, int par, int num) {
    if (re[nd] != curreg) prec[s[curreg]][re[nd]] += num;
    num += re[nd] == curreg;

    int num_current = re[nd] == curreg;
    for (auto i : adj[nd])
        if (i != par)
            num_current += dfs2(i, nd, num);

    if (re[nd] != curreg) prec2[re[nd]][s[curreg]] += num_current;
    return num_current;    
}

int qry(int a, int b) {
    int cnt = 0, num = 0;
    int c1 = 0, c2 = 0, c3 = 0;
    while (c2 < sts[b].size() && c3 < ens[a].size()) {
        int nxt = min(min((c1 < sts[a].size() ? sts[a][c1] : INF), sts[b][c2]), ens[a][c3]);
        if (ens[a][c3] == nxt) { cnt--; c3++; continue; }
        if (c1 < sts[a].size() && sts[a][c1] == nxt) { cnt++; c1++; continue; }
        if (sts[b][c2] == nxt) { num += cnt; c2++; continue; }
    }
    return num;
}

signed main() {
    cin.tie(nullptr) -> ios::sync_with_stdio(false);
    fill(s, s+maxr, -1); 

    cin >> n >> r >> q;
    cin >> re[0]; re[0]--;
    for (int i = 1; i < n; i++) 
        { int a; cin >> a >> re[i]; a--, re[i]--; adj[a].push_back(i); }

    dfs(0, 0);
    for (int i = 0; i < r; i++)
        if (sts[i].size() >= sqrtn) {
            s[i] = cnt2++; curreg = i;
            dfs2(0, 0, 0);   
        }

    for (int i = 0; i < q; i++) {
        int a, b; cin >> a >> b; a--, b--;
        if (s[a] != -1) {cout << prec[s[a]][b] << endl; continue;}
        if (s[b] != -1) {cout << prec2[a][s[b]] << endl; continue;}
        cout << qry(a, b) << endl;
    }
}

Compilation message (stderr)

regions.cpp: In function 'long long int qry(long long int, long long int)':
regions.cpp:49:15: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |     while (c2 < sts[b].size() && c3 < ens[a].size()) {
      |            ~~~^~~~~~~~~~~~~~~
regions.cpp:49:37: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |     while (c2 < sts[b].size() && c3 < ens[a].size()) {
      |                                  ~~~^~~~~~~~~~~~~~~
regions.cpp:50:31: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |         int nxt = min(min((c1 < sts[a].size() ? sts[a][c1] : INF), sts[b][c2]), ens[a][c3]);
      |                            ~~~^~~~~~~~~~~~~~~
regions.cpp:52:16: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |         if (c1 < sts[a].size() && sts[a][c1] == nxt) { cnt++; c1++; continue; }
      |             ~~~^~~~~~~~~~~~~~~

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