oj.uz

Submission #165675

# Submission time Handle Problem Language Result Execution time Memory
165675 2019-11-28T08:18:53 Z nvmdava Regions (IOI09_regions) C++17
100 / 100
 4298 ms 34888 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ff first
#define ss second
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define INF 0x3f3f3f3f3f3f3f3f
#define MOD 1000000007
#define N 200005
#define S 500

int h[N], p[N], ho[N];
vector<int> ch[N];
int le[N], ri[N];
int cntr;

int rs[25005];
vector<int> rid[25005];
vector<pair<pair<int, int>, int> > rrange[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;

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){
            rrange[v].push_back({{le, x.ff - 1}, now});
        }
        now += x.ss;
        le = x.ff;
    }
}

map<int, int> cache;

int main(){
    // ios_base::sync_with_stdio(0);
    // cin.tie(0);
    // cout.tie(0);

    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;
        // if((rs[r1] >= S && rs[r2] >= S) || (rs[r1] < S && rs[r2] < S)){
            int i = 0;
            for(auto& x : rid[r2]){
                while(rrange[r1].size() > i && rrange[r1][i].ff.ss < x)
                    ++i;
                if(rrange[r1].size() == i)
                    break;
                if(rrange[r1].size() != i && rrange[r1][i].ff.ff <= x)
                    ans += rrange[r1][i].ss;
            }
        // }
        cache[r1 * 25000 + r2] = ans;
        printf("%d\n", ans);
        fflush(stdout);
    }
}

Compilation message

regions.cpp: In function 'int main()':
regions.cpp:86:41: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 while(rrange[r1].size() > i && rrange[r1][i].ff.ss < x)
                       ~~~~~~~~~~~~~~~~~~^~~
regions.cpp:88:38: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 if(rrange[r1].size() == i)
                    ~~~~~~~~~~~~~~~~~~^~~~
regions.cpp:90:38: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 if(rrange[r1].size() != i && rrange[r1][i].ff.ff <= x)
                    ~~~~~~~~~~~~~~~~~~^~~~
regions.cpp:58: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:61: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:75: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 6136 KB Output is correct
2 Correct 7 ms 6136 KB Output is correct
3 Correct 8 ms 6136 KB Output is correct
4 Correct 11 ms 6240 KB Output is correct
5 Correct 15 ms 6280 KB Output is correct
6 Correct 30 ms 6392 KB Output is correct
7 Correct 42 ms 6440 KB Output is correct
8 Correct 46 ms 6520 KB Output is correct
9 Correct 65 ms 6916 KB Output is correct
10 Correct 75 ms 7220 KB Output is correct
11 Correct 137 ms 7848 KB Output is correct
12 Correct 160 ms 8460 KB Output is correct
13 Correct 188 ms 8160 KB Output is correct
14 Correct 221 ms 9084 KB Output is correct
15 Correct 258 ms 11000 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1030 ms 13464 KB Output is correct
2 Correct 1222 ms 12888 KB Output is correct
3 Correct 1905 ms 17076 KB Output is correct
4 Correct 315 ms 9756 KB Output is correct
5 Correct 443 ms 11560 KB Output is correct
6 Correct 784 ms 11700 KB Output is correct
7 Correct 729 ms 12624 KB Output is correct
8 Correct 1247 ms 19244 KB Output is correct
9 Correct 2017 ms 26068 KB Output is correct
10 Correct 2831 ms 30896 KB Output is correct
11 Correct 3038 ms 28940 KB Output is correct
12 Correct 1807 ms 24880 KB Output is correct
13 Correct 2733 ms 26620 KB Output is correct
14 Correct 3166 ms 27940 KB Output is correct
15 Correct 3841 ms 32924 KB Output is correct
16 Correct 4298 ms 34888 KB Output is correct
17 Correct 3687 ms 34540 KB Output is correct