oj.uz

Submission #355539

# Submission time Handle Problem Language Result Execution time Memory
355539 2021-01-22T16:53:46 Z parsabahrami Regions (IOI09_regions) C++17
3 / 100
 3449 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], Cdown[N], C1[N], C2[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);
        unordered_map<int, int> tmp = Cdown[u];
        if (SZ(tmp) > SZ(Cdown[v])) Cdown[v].swap(tmp);
        for (pii x : tmp) Cdown[v][x.F] += x.S;
        if (S[A[u]] > SQ) Cdown[v][A[u]]++;
    }
}

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]) C1[A[i]][x.F] += x.S;
        for (pii x : Cdown[i]) C2[A[i]][x.F] += x.S;
    }
    for (; q; q--) {
        int r1, r2; scanf("%d%d", &r1, &r2);
        if (S[r1] > SQ) printf("%d\n", C1[r2][r1]);
        else if (S[r2] > SQ) printf("%d\n", C2[r1][r2]);
        else {
            int l = 0, r = 0, ret = 0;
            for (pii x : vec[r1]) {
                int v = x.S;
                while (r < S[r2] && vec[r2][r].F < Ft[v]) r++;
                while (l < r && vec[r2][l].F < St[v]) l++;
                if (l == S[r2]) continue;
                int u = vec[r2][l].S; 
                if (St[v] <= St[u] && Ft[u] <= Ft[v]) ret += r - l;
            }
            printf("%d\n", ret);
        }
        fflush(stdout);
    }
    return 0;   
}

Compilation message

regions.cpp: In function 'int main()':
regions.cpp:40:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   40 |     scanf("%d%d%d%d", &n, &R, &q, &A[1]);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
regions.cpp:42:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   42 |         int p; scanf("%d%d", &p, &A[i]);
      |                ~~~~~^~~~~~~~~~~~~~~~~~~
regions.cpp:54:26: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   54 |         int r1, r2; scanf("%d%d", &r1, &r2);
      |                     ~~~~~^~~~~~~~~~~~~~~~~~

Subtask #1
3.0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 38 ms 53612 KB Output isn't correct
2 Incorrect 38 ms 53612 KB Output isn't correct
3 Incorrect 40 ms 53612 KB Output isn't correct
4 Incorrect 44 ms 53612 KB Output isn't correct
5 Incorrect 46 ms 53612 KB Output isn't correct
6 Correct 60 ms 53740 KB Output is correct
7 Incorrect 73 ms 53612 KB Output isn't correct
8 Incorrect 72 ms 53740 KB Output isn't correct
9 Correct 83 ms 54764 KB Output is correct
10 Incorrect 125 ms 54124 KB Output isn't correct
11 Incorrect 136 ms 54528 KB Output isn't correct
12 Incorrect 203 ms 55532 KB Output isn't correct
13 Incorrect 210 ms 54636 KB Output isn't correct
14 Incorrect 287 ms 55276 KB Output isn't correct
15 Correct 324 ms 63468 KB Output is correct

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Runtime error 169 ms 131076 KB Execution killed with signal 9
2 Incorrect 1584 ms 116332 KB Output isn't correct
3 Runtime error 181 ms 131076 KB Execution killed with signal 9
4 Incorrect 311 ms 55404 KB Output isn't correct
5 Incorrect 385 ms 60396 KB Output isn't correct
6 Runtime error 152 ms 131076 KB Execution killed with signal 9
7 Incorrect 1451 ms 124524 KB Output isn't correct
8 Runtime error 172 ms 131076 KB Execution killed with signal 9
9 Incorrect 2266 ms 65388 KB Output isn't correct
10 Runtime error 193 ms 131076 KB Execution killed with signal 9
11 Incorrect 3449 ms 62700 KB Output isn't correct
12 Incorrect 1527 ms 100368 KB Output isn't correct
13 Incorrect 1974 ms 100884 KB Output isn't correct
14 Runtime error 255 ms 131076 KB Execution killed with signal 9
15 Incorrect 3146 ms 119640 KB Output isn't correct
16 Runtime error 222 ms 131072 KB Execution killed with signal 9
17 Runtime error 203 ms 131076 KB Execution killed with signal 9