Submission #1228846

#	Time	Username	Problem	Language	Result	Execution time	Memory
1228846		CrabCNH	Regions (IOI09_regions)	C++20	100 / 100	2609 ms	46700 KiB

regions

#include <bits/stdc++.h>

#define task     "BriantheCrab"

#define pii    pair <int, int>
#define fi     first
#define se     second
#define szf    sizeof
#define sz(s)  (int)((s).size())
#define all(v) (v).begin(), (v).end()

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

using namespace std;

template <class T> void minimize (T &t, T f) {if (t > f) t = f;}
template <class T> void maximize (T &t, T f) {if (t < f) t = f;}

const int maxN = 2e5 + 5;
const int inf = 1e18 + 7;
const int mod = 1e9 + 7;
const int base = 450;

// khong tu code thi khong kha len duoc dau

int n, R, q;
int a[maxN];
vector <int> adj[maxN];
int gr[maxN];
int tIn[maxN], tOut[maxN];
vector <int> cc[maxN], tcc[maxN];
int timer = 0;
int par[maxN], sum[maxN];
vector <int> res[maxN];

void dfsPre (int u, int p) {
    tIn[u] = ++timer;
    cc[gr[u]].push_back (u);
    for (auto v : adj[u]) {
        if (v == p) {
            continue;
        }
        dfsPre (v, u);
    }
    tOut[u] = timer;
}

void dfs (int u, int p, int curS, int r) {
    for (auto v : adj[u]) {
        if (v == p) {
            continue;
        }
        sum[gr[v]] += curS;
        //cout << "gay " << v << ' ' << gr[v] << ' ' << curS << '\n';
        dfs (v, u, curS + (gr[v] == r), r);
    }
}

void solve () {
    cin >> n >> R >> q;
    cin >> gr[1];
    par[1] = 0;
    for (int i = 2; i <= n; i ++) {
        int p;
        cin >> p >> gr[i];
        par[i] = p;
        adj[p].push_back (i);
        adj[i].push_back (p);
        //cout << i << ' ' << p << '\n';
    }
    dfsPre (1, 1);
    for (int r = 1; r <= R; r++){
        tcc[r].reserve (cc[r].size());
        for (int u : cc[r]){
            tcc[r].push_back (tIn[u]);
        }
        sort(tcc[r].begin(), tcc[r].end());
    }
    for (int i = 1; i <= q; i ++) {
        int r1, r2;
        cin >> r1 >> r2;
        if (sz (tcc[r1]) < base) {
            int res = 0;
            for (auto u : cc[r1]) {
                int lPos = lower_bound (all (tcc[r2]), tIn[u]) - tcc[r2].begin ();
                int rPos = upper_bound (all (tcc[r2]), tOut[u]) - tcc[r2].begin ();
                res += (rPos - lPos);
                //cout << r << ' ' << l << '\n';
            }
            cout << res << '\n' << flush;
        }
        else {
            if (res[r1].empty ()) {
                int rt = 0;
                dfs (1, 1, gr[1] == r1, r1);
                for (int i = 1; i <= R; i ++) {
                    res[r1].push_back (sum[i]);
                    //cout << sum[i] << ' ';
                    sum[i] = 0;
                }
            }
            cout << res[r1][r2 - 1] << '\n' << flush;
        }
    }
    return;
}

signed main () {
    cin.tie (nullptr) -> sync_with_stdio (false);
    if (fopen (task".inp", "r")) {
        freopen (task".inp", "r", stdin);
        freopen (task".out", "w", stdout);
    }
    int t = 1;
    //cin >> t;
    while (t --) {
        solve ();
    } 
    return 0;
}
// thfv

Compilation message (stderr)

regions.cpp:22:22: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   22 | const int inf = 1e18 + 7;
      |                 ~~~~~^~~
regions.cpp: In function 'int main()':
regions.cpp:113:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  113 |         freopen (task".inp", "r", stdin);
      |         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
regions.cpp:114:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  114 |         freopen (task".out", "w", stdout);
      |         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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