oj.uz

Submission #542592

# Submission time Handle Problem Language Result Execution time Memory
542592 2022-03-27T03:29:35 Z Netr Regions (IOI09_regions) C++14
7 / 100
 8000 ms 131072 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pi;

#ifdef DEBUG
#define D(x...) printf(x);
#else
#define D(x...)
#endif

#define lsb(x) (x&(-x))

const int MAXN = 2e5 + 5;
const int MAXR = 3e4 + 5;

int N, R, Q, regions[MAXN], tour[MAXN], tme[MAXN][2], timer = 1;
vector<int> adj[MAXN];
map<pi,int> queries;
map<int,int> tdft[MAXN], buft[MAXN];
vector<int> pbr[MAXR];

void updatetd(int p, int t, int v){
    for(; p <= N; p += lsb(p)){
        if(tdft[p].count(t)){
            tdft[p][t] += v;
        }else{
            tdft[p][t] = v;
        }
    }
}

int querytd(int p, int t){
    int res = 0;
    for(; p != 0; p -= lsb(p)){
        if(tdft[p].count(t)){
            res += tdft[p][t];
        }
    }
    return res;
}

int rangeQuerytd(int l, int r, int t){
    return querytd(r, t) - querytd(l-1, t);
}

void updatebu(int p, int t, int v){
    for(; p <= N; p += lsb(p)){
        if(buft[p].count(t)){
            buft[p][t] += v;
        }else{
            buft[p][t] = v;
        }
    }
}

void rangeUpdatebu(int l, int r, int t, int v){
    updatebu(l, t, v);
    updatebu(r+1, t, -v);
}

int querybu(int p, int t){
    int res = 0;
    for(; p != 0; p -= lsb(p)){
        if(buft[p].count(t)){
            res += buft[p][t];
        }
    }
    return res;
}

void dfs(int n, int p = 1){
    tour[timer] = n;
    tme[n][0] = timer++;

    for(int e : adj[n]){
        if(e == p) continue;
        dfs(e, n);
    }

    tme[n][1] = timer-1;
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    cin >> N >> R >> Q >> regions[1];
    for(int i = 2; i <= N; i++){
        int sk, hk;
        cin >> sk >> hk;
        adj[sk].push_back(i);
        adj[i].push_back(sk);
        regions[i] = hk;
        pbr[hk].push_back(i);
    }

    dfs(1);
   
    for(int i = 1; i <= N; i++){
        updatetd(i, regions[tour[i]], 1);
        rangeUpdatebu(tme[i][0], tme[i][1], regions[i], 1);
    }

    D("Euler tour: ")
    for(int i = 1; i <= N; i++){
        D("%d ", tour[i]);
    }
    D("\ntd ft queries:\n");
    for(int i = 1; i <= N; i++){
        for(int j = 1; j <= R; j++){
            D("Person %d, region %d = %d\n", i, j, rangeQuerytd(tme[i][0], tme[i][1], j));
        }
    }
    D("\nbu ft queries:\n");
    for(int i = 1; i <= N; i++){
        for(int j = 1; j <= R; j++){
            D("Person %d, region %d = %d\n", i, j, querybu(tme[i][0], j));
        }
    }

    for(int z = 0; z < Q; z++){
        int r1, r2;
        cin >> r1 >> r2;
        if(queries.count({r1,r2})){
            cout << queries[{r1,r2}] << "\n";
            cout.flush();
            continue;
        }
        int ans = 0;
        if(r1 >= r2){
            // top down
            for(int i : pbr[r1]){
                ans += rangeQuerytd(tme[i][0], tme[i][1], r2); 
            }
        }else{
            // bottom up
            for(int i : pbr[r2]){
                ans += querybu(tme[i][0], r1);
            }
        }
        queries[{r1,r2}] = ans;
        cout << ans << "\n";
        cout.flush();
    }
}

Subtask #1
2.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 24512 KB Output is correct
2 Incorrect 14 ms 24528 KB Output isn't correct
3 Incorrect 16 ms 24544 KB Output isn't correct
4 Incorrect 18 ms 24528 KB Output isn't correct
5 Incorrect 22 ms 24676 KB Output isn't correct
6 Incorrect 37 ms 24984 KB Output isn't correct
7 Incorrect 61 ms 25504 KB Output isn't correct
8 Incorrect 85 ms 25844 KB Output isn't correct
9 Incorrect 105 ms 27548 KB Output isn't correct
10 Correct 304 ms 31168 KB Output is correct
11 Incorrect 704 ms 34288 KB Output isn't correct
12 Incorrect 997 ms 37764 KB Output isn't correct
13 Incorrect 1542 ms 39160 KB Output isn't correct
14 Incorrect 2550 ms 42156 KB Output isn't correct
15 Incorrect 3379 ms 47176 KB Output isn't correct

Subtask #2
5.0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 8080 ms 60324 KB Time limit exceeded
2 Execution timed out 8051 ms 62768 KB Time limit exceeded
3 Execution timed out 8023 ms 69160 KB Time limit exceeded
4 Incorrect 2738 ms 46784 KB Output isn't correct
5 Incorrect 2784 ms 52964 KB Output isn't correct
6 Incorrect 3130 ms 61768 KB Output isn't correct
7 Correct 3486 ms 81008 KB Output is correct
8 Execution timed out 8080 ms 95280 KB Time limit exceeded
9 Runtime error 861 ms 131072 KB Execution killed with signal 9
10 Runtime error 841 ms 131072 KB Execution killed with signal 9
11 Runtime error 843 ms 131072 KB Execution killed with signal 9
12 Runtime error 913 ms 131072 KB Execution killed with signal 9
13 Runtime error 815 ms 131072 KB Execution killed with signal 9
14 Runtime error 899 ms 131072 KB Execution killed with signal 9
15 Runtime error 827 ms 131072 KB Execution killed with signal 9
16 Runtime error 829 ms 131072 KB Execution killed with signal 9
17 Runtime error 816 ms 131072 KB Execution killed with signal 9