oj.uz

Submission #355565

# Submission time Handle Problem Language Result Execution time Memory
355565 2021-01-22T17:28:35 Z parsabahrami Regions (IOI09_regions) C++17
100 / 100
 5068 ms 80748 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 = 1500;
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 21 ms 28524 KB Output is correct
2 Correct 20 ms 28524 KB Output is correct
3 Correct 23 ms 28524 KB Output is correct
4 Correct 23 ms 28524 KB Output is correct
5 Correct 32 ms 28524 KB Output is correct
6 Correct 39 ms 28652 KB Output is correct
7 Correct 47 ms 28652 KB Output is correct
8 Correct 47 ms 28652 KB Output is correct
9 Correct 70 ms 29164 KB Output is correct
10 Correct 104 ms 29036 KB Output is correct
11 Correct 143 ms 29420 KB Output is correct
12 Correct 207 ms 29932 KB Output is correct
13 Correct 199 ms 29548 KB Output is correct
14 Correct 296 ms 30188 KB Output is correct
15 Correct 320 ms 33900 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 2169 ms 44140 KB Output is correct
2 Correct 2921 ms 43244 KB Output is correct
3 Correct 3647 ms 78252 KB Output is correct
4 Correct 290 ms 30188 KB Output is correct
5 Correct 498 ms 32492 KB Output is correct
6 Correct 1644 ms 31596 KB Output is correct
7 Correct 2062 ms 32492 KB Output is correct
8 Correct 1715 ms 39404 KB Output is correct
9 Correct 2885 ms 38380 KB Output is correct
10 Correct 5068 ms 45036 KB Output is correct
11 Correct 5032 ms 37356 KB Output is correct
12 Correct 1716 ms 56940 KB Output is correct
13 Correct 2435 ms 57632 KB Output is correct
14 Correct 3458 ms 57888 KB Output is correct
15 Correct 4525 ms 63772 KB Output is correct
16 Correct 4406 ms 73012 KB Output is correct
17 Correct 4217 ms 80748 KB Output is correct