oj.uz

Submission #355551

# Submission time Handle Problem Language Result Execution time Memory
355551 2021-01-22T17:10:58 Z parsabahrami Regions (IOI09_regions) C++17
75 / 100
 5879 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 = 450;
unordered_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;
    }
    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:49:26: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   49 |         int r1, r2; scanf("%d%d", &r1, &r2);
      |                     ~~~~~^~~~~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 31596 KB Output is correct
2 Correct 22 ms 31596 KB Output is correct
3 Correct 24 ms 31596 KB Output is correct
4 Correct 25 ms 31596 KB Output is correct
5 Correct 30 ms 31724 KB Output is correct
6 Correct 49 ms 31724 KB Output is correct
7 Correct 55 ms 31724 KB Output is correct
8 Correct 54 ms 31724 KB Output is correct
9 Correct 72 ms 32256 KB Output is correct
10 Correct 125 ms 32236 KB Output is correct
11 Correct 166 ms 32492 KB Output is correct
12 Correct 193 ms 33004 KB Output is correct
13 Correct 253 ms 32768 KB Output is correct
14 Correct 306 ms 33260 KB Output is correct
15 Correct 433 ms 36460 KB Output is correct

Subtask #2
60.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1979 ms 88132 KB Output is correct
2 Correct 2629 ms 82240 KB Output is correct
3 Correct 3404 ms 75320 KB Output is correct
4 Correct 363 ms 33260 KB Output is correct
5 Correct 430 ms 35308 KB Output is correct
6 Runtime error 179 ms 131076 KB Execution killed with signal 9
7 Correct 2165 ms 81772 KB Output is correct
8 Runtime error 174 ms 131072 KB Execution killed with signal 9
9 Correct 2948 ms 41324 KB Output is correct
10 Runtime error 198 ms 131072 KB Execution killed with signal 9
11 Correct 5879 ms 40528 KB Output is correct
12 Correct 2067 ms 61272 KB Output is correct
13 Correct 2518 ms 61736 KB Output is correct
14 Runtime error 284 ms 131072 KB Execution killed with signal 9
15 Correct 4540 ms 68196 KB Output is correct
16 Correct 4093 ms 75476 KB Output is correct
17 Runtime error 220 ms 131076 KB Execution killed with signal 9