oj.uz

Submission #355561

# Submission time Handle Problem Language Result Execution time Memory
355561 2021-01-22T17:25:17 Z parsabahrami Regions (IOI09_regions) C++17
90 / 100
 5471 ms 131076 KB 
// Call my Name and Save me from The Dark
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")

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 = 750;
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:37:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   37 |     scanf("%d%d%d%d", &n, &R, &q, &A[1]);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
regions.cpp:39:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   39 |         int p; scanf("%d%d", &p, &A[i]);
      |                ~~~~~^~~~~~~~~~~~~~~~~~~
regions.cpp:51:26: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   51 |         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 20 ms 28524 KB Output is correct
3 Correct 22 ms 28524 KB Output is correct
4 Correct 25 ms 28524 KB Output is correct
5 Correct 28 ms 28524 KB Output is correct
6 Correct 43 ms 28652 KB Output is correct
7 Correct 56 ms 28652 KB Output is correct
8 Correct 63 ms 28652 KB Output is correct
9 Correct 82 ms 29164 KB Output is correct
10 Correct 122 ms 29036 KB Output is correct
11 Correct 143 ms 29548 KB Output is correct
12 Correct 205 ms 29932 KB Output is correct
13 Correct 197 ms 29548 KB Output is correct
14 Correct 264 ms 30188 KB Output is correct
15 Correct 376 ms 33932 KB Output is correct

Subtask #2
75.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 2345 ms 44140 KB Output is correct
2 Correct 2634 ms 69232 KB Output is correct
3 Correct 3732 ms 78252 KB Output is correct
4 Correct 379 ms 30188 KB Output is correct
5 Correct 523 ms 32492 KB Output is correct
6 Correct 1631 ms 31468 KB Output is correct
7 Correct 2116 ms 32492 KB Output is correct
8 Correct 1664 ms 39404 KB Output is correct
9 Correct 2974 ms 38380 KB Output is correct
10 Correct 5130 ms 45092 KB Output is correct
11 Correct 5471 ms 37356 KB Output is correct
12 Correct 1886 ms 56940 KB Output is correct
13 Correct 2959 ms 57620 KB Output is correct
14 Runtime error 251 ms 131076 KB Execution killed with signal 9
15 Correct 4527 ms 63704 KB Output is correct
16 Correct 4062 ms 72968 KB Output is correct
17 Runtime error 205 ms 131076 KB Execution killed with signal 9