oj.uz

Submission #165679

# Submission time Handle Problem Language Result Execution time Memory
165679 2019-11-28T08:29:28 Z nvmdava Regions (IOI09_regions) C++17
100 / 100
 4334 ms 34904 KB 
#include <bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define N 200005

int h[N], p[N], ho[N], le[N], ri[N], cntr;

int rs[25005];
vector<int> rid[25005], ch[N];
vector<pair<pair<int, int>, int> > rra[25005];

void dfs(int v){
    int t = ++cntr;
    rid[h[v]].push_back(cntr);
    ho[cntr] = h[v];
    for(auto& x : ch[v])
        dfs(x);
    ri[t] = cntr;
}

map<int, int> dif, cache;

void addrange(int v){
    dif.clear();
    for(auto& x : rid[v]){
        ++dif[x];
        --dif[ri[x] + 1];
    }

    int now = 0, le = -1;

    for(auto& x : dif){
        if(now != 0){
            rra[v].push_back({{le, x.ff - 1}, now});
        }
        now += x.ss;
        le = x.ff;
    }
}


int main(){
    int n, r, q;
    scanf("%d%d%d%d", &n, &r, &q, &h[1]);
    ++rs[h[1]];
    for(int i = 2; i <= n; ++i){
        scanf("%d%d", &p[i], &h[i]);
        ++rs[h[i]];
        ch[p[i]].push_back(i);
    }

    dfs(1);
    cntr = 0;
    for(int i = 1; i <= r; ++i)
        addrange(i);
    


    while(q--){
        int r1, r2;
        scanf("%d%d", &r1, &r2);
        auto it = cache.find(r1 * 25000 + r2);
        if(it != cache.end()){
            printf("%d\n", it -> ss);
            fflush(stdout);
            continue;
        }
        int ans = 0, i = 0;
        for(auto& x : rid[r2]){
            while(rra[r1].size() > i && rra[r1][i].ff.ss < x)
                ++i;
            if(rra[r1].size() == i)
                break;
            if(rra[r1].size() != i && rra[r1][i].ff.ff <= x)
                ans += rra[r1][i].ss;
        }
        cache[r1 * 25000 + r2] = ans;
        printf("%d\n", ans);
        fflush(stdout);
    }
}

Compilation message

regions.cpp: In function 'int main()':
regions.cpp:72:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             while(rra[r1].size() > i && rra[r1][i].ff.ss < x)
                   ~~~~~~~~~~~~~~~^~~
regions.cpp:74:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             if(rra[r1].size() == i)
                ~~~~~~~~~~~~~~~^~~~
regions.cpp:76:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             if(rra[r1].size() != i && rra[r1][i].ff.ff <= x)
                ~~~~~~~~~~~~~~~^~~~
regions.cpp:46:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d%d%d", &n, &r, &q, &h[1]);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
regions.cpp:49:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &p[i], &h[i]);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~
regions.cpp:63:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &r1, &r2);
         ~~~~~^~~~~~~~~~~~~~~~~~

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 6136 KB Output is correct
3 Correct 17 ms 6140 KB Output is correct
4 Correct 11 ms 6136 KB Output is correct
5 Correct 15 ms 6264 KB Output is correct
6 Correct 32 ms 6264 KB Output is correct
7 Correct 41 ms 6392 KB Output is correct
8 Correct 29 ms 6524 KB Output is correct
9 Correct 73 ms 6908 KB Output is correct
10 Correct 122 ms 7340 KB Output is correct
11 Correct 161 ms 7732 KB Output is correct
12 Correct 186 ms 8544 KB Output is correct
13 Correct 170 ms 8220 KB Output is correct
14 Correct 220 ms 9208 KB Output is correct
15 Correct 284 ms 11052 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1106 ms 13428 KB Output is correct
2 Correct 1156 ms 12960 KB Output is correct
3 Correct 1730 ms 16948 KB Output is correct
4 Correct 351 ms 9736 KB Output is correct
5 Correct 468 ms 11440 KB Output is correct
6 Correct 716 ms 11672 KB Output is correct
7 Correct 1029 ms 12500 KB Output is correct
8 Correct 1222 ms 19228 KB Output is correct
9 Correct 1987 ms 26052 KB Output is correct
10 Correct 2726 ms 30896 KB Output is correct
11 Correct 3285 ms 28684 KB Output is correct
12 Correct 1978 ms 24956 KB Output is correct
13 Correct 2587 ms 26824 KB Output is correct
14 Correct 3075 ms 28112 KB Output is correct
15 Correct 4003 ms 32772 KB Output is correct
16 Correct 4334 ms 34904 KB Output is correct
17 Correct 3790 ms 34612 KB Output is correct