oj.uz

Submission #74318

# Submission time Handle Problem Language Result Execution time Memory
74318 2018-08-31T09:25:50 Z Bruteforceman Regions (IOI09_regions) C++11
100 / 100
 6990 ms 75460 KB 
#pragma GCC optimize("Ofast")
#include "bits/stdc++.h"
using namespace std;
int N, R, Q;
int a[200010], p[200010];
const int magic = 200;
const int chunk = 5 + (200000 / magic);
int ans[chunk][25001];
vector <int> g[200010];

int idx[25001];
int current;
int tot[25001];

void dfs(int x, int cnt) {
    cnt += (current == a[x]);
    if(a[x] != current) {
        ans[idx[current]][a[x]] += cnt;
    }
    for(auto i : g[x]) {
        dfs(i, cnt);
    }
} 

int in[200010];
int out[200010];
vector <int> v[25001];
vector <int> nodes[25001];
int cur;

void go(int x) {
    in[x] = ++cur;
    v[a[x]].emplace_back(in[x]);
    for(auto i : g[x]) {
        go(i);
    }
    out[x] = cur;
}
int count(int l, int r, int val) {
    return upper_bound(v[val].begin(), v[val].end(), r) - lower_bound(v[val].begin(), v[val].end(), l);
}

int main(int argc, char const *argv[])
{
    scanf("%d %d %d", &N, &R, &Q);
    for(int i = 1; i <= N; i++) {
        if(i == 1) scanf("%d", &a[i]);
        else scanf("%d %d", &p[i], &a[i]);
    }
    for(int i = 2; i <= N; i++) {
        g[p[i]].emplace_back(i);
    }
    for(int i = 1; i <= N; i++) {
        tot[a[i]] += 1;
        nodes[a[i]].emplace_back(i);
    }
    int now = 0;
    for(int i = 1; i <= R; i++) {
        if(tot[i] > magic) {
            current = i;
            idx[i] = now++; 
            dfs(1, 0);
        }
    }
    go(1);
    while(Q--) {
        int p, q;
        scanf("%d %d", &p, &q);
        if(tot[p] > magic) {
            printf("%d\n", ans[idx[p]][q]);
        } else {
            int res = 0;
            for(int i : nodes[p]) {
                res += count(in[i], out[i], q);
            }
            printf("%d\n", res);
        }
        fflush(stdout);
    }
    return 0;
}

Compilation message

regions.cpp: In function 'int main(int, const char**)':
regions.cpp:45:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d %d", &N, &R, &Q);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
regions.cpp:47:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         if(i == 1) scanf("%d", &a[i]);
                    ~~~~~^~~~~~~~~~~~~
regions.cpp:48:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         else scanf("%d %d", &p[i], &a[i]);
              ~~~~~^~~~~~~~~~~~~~~~~~~~~~~
regions.cpp:68:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", &p, &q);
         ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 6264 KB Output is correct
2 Correct 8 ms 6264 KB Output is correct
3 Correct 7 ms 6292 KB Output is correct
4 Correct 10 ms 6440 KB Output is correct
5 Correct 13 ms 6440 KB Output is correct
6 Correct 16 ms 6496 KB Output is correct
7 Correct 27 ms 6496 KB Output is correct
8 Correct 35 ms 6544 KB Output is correct
9 Correct 48 ms 6816 KB Output is correct
10 Correct 49 ms 6968 KB Output is correct
11 Correct 102 ms 7252 KB Output is correct
12 Correct 141 ms 7696 KB Output is correct
13 Correct 184 ms 7696 KB Output is correct
14 Correct 367 ms 8096 KB Output is correct
15 Correct 394 ms 10160 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1551 ms 11596 KB Output is correct
2 Correct 932 ms 11596 KB Output is correct
3 Correct 3557 ms 12860 KB Output is correct
4 Correct 272 ms 12860 KB Output is correct
5 Correct 388 ms 12860 KB Output is correct
6 Correct 542 ms 12860 KB Output is correct
7 Correct 1287 ms 13012 KB Output is correct
8 Correct 1112 ms 19312 KB Output is correct
9 Correct 2613 ms 22740 KB Output is correct
10 Correct 3130 ms 55448 KB Output is correct
11 Correct 5479 ms 75460 KB Output is correct
12 Correct 6990 ms 75460 KB Output is correct
13 Correct 3656 ms 75460 KB Output is correct
14 Correct 2813 ms 75460 KB Output is correct
15 Correct 4042 ms 75460 KB Output is correct
16 Correct 2335 ms 75460 KB Output is correct
17 Correct 3387 ms 75460 KB Output is correct