oj.uz

Submission #355553

# Submission time Handle Problem Language Result Execution time Memory
355553 2021-01-22T17:14:47 Z parsabahrami Regions (IOI09_regions) C++17
90 / 100
 5755 ms 131076 KB 
// 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 = 510;
map<int, int> Cup[N], C[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);
    }
}

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]) C[A[i]][x.F] += x.S;
        Cup[i].clear();
    }
    for (; q; q--) {
        int r1, r2; scanf("%d%d", &r1, &r2);
        if (S[r1] > SQ) printf("%d\n", C[r2][r1]);
        else {
            int ret = 0;
            for (pii x : vec[r1]) {
                int v = x.S;
                int l = lower_bound(vec[r2].begin(), vec[r2].end(), pii(St[v], -1e9)) - vec[r2].begin();
                int r = upper_bound(vec[r2].begin(), vec[r2].end(), pii(Ft[v], -1e9)) - vec[r2].begin();
                ret += r - l;
            }
            printf("%d\n", ret);
        }
        fflush(stdout);
    }
    return 0;   
}

Compilation message

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

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 28524 KB Output is correct
2 Correct 19 ms 28524 KB Output is correct
3 Correct 22 ms 28524 KB Output is correct
4 Correct 27 ms 28524 KB Output is correct
5 Correct 25 ms 28524 KB Output is correct
6 Correct 43 ms 28652 KB Output is correct
7 Correct 45 ms 28652 KB Output is correct
8 Correct 50 ms 28652 KB Output is correct
9 Correct 87 ms 29292 KB Output is correct
10 Correct 126 ms 29060 KB Output is correct
11 Correct 169 ms 29420 KB Output is correct
12 Correct 207 ms 30060 KB Output is correct
13 Correct 238 ms 29548 KB Output is correct
14 Correct 357 ms 30188 KB Output is correct
15 Correct 396 ms 34540 KB Output is correct

Subtask #2
75.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 2366 ms 76012 KB Output is correct
2 Correct 2699 ms 76652 KB Output is correct
3 Correct 3621 ms 78812 KB Output is correct
4 Correct 354 ms 30188 KB Output is correct
5 Correct 482 ms 33004 KB Output is correct
6 Correct 1617 ms 31596 KB Output is correct
7 Correct 2052 ms 32620 KB Output is correct
8 Correct 1491 ms 40428 KB Output is correct
9 Correct 2185 ms 38764 KB Output is correct
10 Correct 5656 ms 46444 KB Output is correct
11 Correct 5755 ms 37484 KB Output is correct
12 Correct 1944 ms 57068 KB Output is correct
13 Correct 2854 ms 57928 KB Output is correct
14 Runtime error 249 ms 131076 KB Execution killed with signal 9
15 Correct 3876 ms 64760 KB Output is correct
16 Correct 3574 ms 75884 KB Output is correct
17 Runtime error 200 ms 131076 KB Execution killed with signal 9