oj.uz

Submission #355543

# Submission time Handle Problem Language Result Execution time Memory
355543 2021-01-22T16:58:03 Z parsabahrami Regions (IOI09_regions) C++17
3 / 100
 2892 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;
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);
        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] || !r) continue;
                int u = vec[r2][l].S, w = vec[r2][r - 1].S;
                if (St[v] <= St[u] && Ft[u] <= Ft[v] && St[v] <= St[w] && Ft[w] <= 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 33 ms 47340 KB Output isn't correct
2 Incorrect 37 ms 47340 KB Output isn't correct
3 Incorrect 33 ms 47340 KB Output isn't correct
4 Incorrect 38 ms 47340 KB Output isn't correct
5 Incorrect 41 ms 47340 KB Output isn't correct
6 Correct 48 ms 47468 KB Output is correct
7 Incorrect 57 ms 47468 KB Output isn't correct
8 Incorrect 78 ms 47468 KB Output isn't correct
9 Correct 84 ms 48620 KB Output is correct
10 Incorrect 144 ms 47852 KB Output isn't correct
11 Incorrect 134 ms 48236 KB Output isn't correct
12 Incorrect 207 ms 49388 KB Output isn't correct
13 Incorrect 168 ms 48364 KB Output isn't correct
14 Incorrect 245 ms 48956 KB Output isn't correct
15 Correct 270 ms 57708 KB Output is correct

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Runtime error 166 ms 131076 KB Execution killed with signal 9
2 Incorrect 1564 ms 111640 KB Output isn't correct
3 Runtime error 171 ms 131076 KB Execution killed with signal 9
4 Incorrect 363 ms 49260 KB Output isn't correct
5 Incorrect 398 ms 54508 KB Output isn't correct
6 Runtime error 155 ms 131076 KB Execution killed with signal 9
7 Incorrect 1440 ms 120556 KB Output isn't correct
8 Runtime error 162 ms 131076 KB Execution killed with signal 9
9 Incorrect 2352 ms 59500 KB Output isn't correct
10 Runtime error 192 ms 131076 KB Execution killed with signal 9
11 Incorrect 2817 ms 56556 KB Output isn't correct
12 Incorrect 1682 ms 93796 KB Output isn't correct
13 Incorrect 1681 ms 94688 KB Output isn't correct
14 Runtime error 259 ms 131076 KB Execution killed with signal 9
15 Incorrect 2892 ms 114408 KB Output isn't correct
16 Runtime error 183 ms 131076 KB Execution killed with signal 9
17 Runtime error 202 ms 131076 KB Execution killed with signal 9