Submission #355539

#	Time	Username	Problem	Language	Result	Execution time	Memory
355539		parsabahrami	Regions (IOI09_regions)	C++17	3 / 100	3449 ms	131076 KiB

regions

// Call my Name and Save me from The Dark
#include <bits/stdc++.h>
 
using namespace std;

typedef long long int ll;
typedef pair<int, int> pii;
 
#define SZ(x)                       (int) x.size()
#define F                           first
#define S                           second

const int N = 2e5 + 10, SQ = 450;
unordered_map<int, int> Cup[N], Cdown[N], C1[N], C2[N]; vector<pii> vec[N];
int A[N], S[N], St[N], Ft[N], n, R, q, tim; vector<int> adj[N];

void preDFS(int v) {
    St[v] = tim++;
    for (int u : adj[v]) {
        preDFS(u);
    }
    Ft[v] = tim;
}

void DFS(int v, int p = -1) {
    if (~p) {
        Cup[v] = Cup[p];
        if (S[A[p]] > SQ) Cup[v][A[p]]++;
    }
    for (int u : adj[v]) {
        DFS(u, v);
        unordered_map<int, int> tmp = Cdown[u];
        if (SZ(tmp) > SZ(Cdown[v])) Cdown[v].swap(tmp);
        for (pii x : tmp) Cdown[v][x.F] += x.S;
        if (S[A[u]] > SQ) Cdown[v][A[u]]++;
    }
}

int main() {
    scanf("%d%d%d%d", &n, &R, &q, &A[1]);
    for (int i = 2; i <= n; i++) {
        int p; scanf("%d%d", &p, &A[i]);
        adj[p].push_back(i);
    }
    preDFS(1);
    for (int i = 1; i <= n; i++) vec[A[i]].push_back({St[i], i});
    for (int i = 1; i <= R; i++) sort(vec[i].begin(), vec[i].end()), S[i] = SZ(vec[i]);
    DFS(1);
    for (int i = 1; i <= n; i++) {
        for (pii x : Cup[i]) C1[A[i]][x.F] += x.S;
        for (pii x : Cdown[i]) C2[A[i]][x.F] += x.S;
    }
    for (; q; q--) {
        int r1, r2; scanf("%d%d", &r1, &r2);
        if (S[r1] > SQ) printf("%d\n", C1[r2][r1]);
        else if (S[r2] > SQ) printf("%d\n", C2[r1][r2]);
        else {
            int l = 0, r = 0, ret = 0;
            for (pii x : vec[r1]) {
                int v = x.S;
                while (r < S[r2] && vec[r2][r].F < Ft[v]) r++;
                while (l < r && vec[r2][l].F < St[v]) l++;
                if (l == S[r2]) continue;
                int u = vec[r2][l].S; 
                if (St[v] <= St[u] && Ft[u] <= Ft[v]) ret += r - l;
            }
            printf("%d\n", ret);
        }
        fflush(stdout);
    }
    return 0;   
}

Compilation message (stderr)

regions.cpp: In function 'int main()':
regions.cpp:40:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   40 |     scanf("%d%d%d%d", &n, &R, &q, &A[1]);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
regions.cpp:42:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   42 |         int p; scanf("%d%d", &p, &A[i]);
      |                ~~~~~^~~~~~~~~~~~~~~~~~~
regions.cpp:54:26: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   54 |         int r1, r2; scanf("%d%d", &r1, &r2);
      |                     ~~~~~^~~~~~~~~~~~~~~~~~

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