oj.uz

Submission #355563

# Submission time Handle Problem Language Result Execution time Memory
355563 2021-01-22T17:27:03 Z parsabahrami Regions (IOI09_regions) C++17
90 / 100
 5459 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 = 900;
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 19 ms 28524 KB Output is correct
2 Correct 20 ms 28524 KB Output is correct
3 Correct 21 ms 28524 KB Output is correct
4 Correct 23 ms 28524 KB Output is correct
5 Correct 27 ms 28524 KB Output is correct
6 Correct 37 ms 28652 KB Output is correct
7 Correct 47 ms 28652 KB Output is correct
8 Correct 50 ms 28652 KB Output is correct
9 Correct 68 ms 29292 KB Output is correct
10 Correct 122 ms 29056 KB Output is correct
11 Correct 149 ms 29420 KB Output is correct
12 Correct 157 ms 30060 KB Output is correct
13 Correct 265 ms 29548 KB Output is correct
14 Correct 336 ms 30188 KB Output is correct
15 Correct 388 ms 34540 KB Output is correct

Subtask #2
75.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 2329 ms 44388 KB Output is correct
2 Correct 2747 ms 65388 KB Output is correct
3 Correct 3603 ms 78800 KB Output is correct
4 Correct 377 ms 30292 KB Output is correct
5 Correct 506 ms 33004 KB Output is correct
6 Correct 1582 ms 31596 KB Output is correct
7 Correct 2124 ms 32620 KB Output is correct
8 Correct 1703 ms 40428 KB Output is correct
9 Correct 2780 ms 38636 KB Output is correct
10 Correct 4708 ms 46400 KB Output is correct
11 Correct 5459 ms 37484 KB Output is correct
12 Correct 1713 ms 56992 KB Output is correct
13 Correct 2702 ms 57916 KB Output is correct
14 Runtime error 252 ms 131076 KB Execution killed with signal 9
15 Correct 4230 ms 64856 KB Output is correct
16 Correct 4103 ms 76036 KB Output is correct
17 Runtime error 226 ms 131076 KB Execution killed with signal 9