oj.uz

Submission #355552

# Submission time Handle Problem Language Result Execution time Memory
355552 2021-01-22T17:12:51 Z parsabahrami Regions (IOI09_regions) C++17
90 / 100
 5477 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 = 500;
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;
        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 21 ms 31596 KB Output is correct
2 Correct 24 ms 31596 KB Output is correct
3 Correct 24 ms 31596 KB Output is correct
4 Correct 27 ms 31596 KB Output is correct
5 Correct 32 ms 31724 KB Output is correct
6 Correct 44 ms 31724 KB Output is correct
7 Correct 61 ms 31676 KB Output is correct
8 Correct 57 ms 31724 KB Output is correct
9 Correct 79 ms 32236 KB Output is correct
10 Correct 122 ms 32236 KB Output is correct
11 Correct 187 ms 32492 KB Output is correct
12 Correct 162 ms 33004 KB Output is correct
13 Correct 286 ms 32748 KB Output is correct
14 Correct 336 ms 33260 KB Output is correct
15 Correct 338 ms 36460 KB Output is correct

Subtask #2
75.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 2291 ms 78664 KB Output is correct
2 Correct 2841 ms 82156 KB Output is correct
3 Correct 3783 ms 75116 KB Output is correct
4 Correct 309 ms 33260 KB Output is correct
5 Correct 542 ms 35308 KB Output is correct
6 Correct 1747 ms 34540 KB Output is correct
7 Correct 2007 ms 35564 KB Output is correct
8 Correct 1503 ms 41452 KB Output is correct
9 Correct 3149 ms 41196 KB Output is correct
10 Correct 5018 ms 46716 KB Output is correct
11 Correct 5477 ms 40428 KB Output is correct
12 Correct 1695 ms 59884 KB Output is correct
13 Correct 2788 ms 60268 KB Output is correct
14 Runtime error 272 ms 131076 KB Execution killed with signal 9
15 Correct 4184 ms 65832 KB Output is correct
16 Correct 4315 ms 73140 KB Output is correct
17 Runtime error 245 ms 131076 KB Execution killed with signal 9