oj.uz

Submission #984994

# Submission time Handle Problem Language Result Execution time Memory
984994 2024-05-17T09:07:57 Z Br3ad Regions (IOI09_regions) C++17
30 / 100
 7311 ms 131072 KB 
#include <iostream>
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <functional>
#include <numeric>
#include <cstring>
#include <string>
#include <cmath>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <map>

using namespace std;
#define ll long long
#define ull unsigned long long
#define f first
#define s second
#define PF push_front
#define PB push_back
#define MP make_pair
#define max(a, b) ((a > b)? a : b)
#define min(a, b) ((a < b)? a : b)
#define max3(a, b, c) max(max(a, b), c)
#define min3(a, b, c) min(min(a, b), c)

const int N = 2e5 + 5;
const int M = 1e9 + 7; 
const int inf = 0x3f3f3f3f;
const ll int INF = 1e18;

struct BIT {
    int sz;
    vector<int> tree;

    BIT(int n) : sz(n+1), tree(n+1, 0) {};

    void add(int pos, int val){
        for(; pos < sz; pos += pos&-pos) tree[pos] += val;
    }

    int sum(int pos){
        int ans = 0;
        for(; pos >= 1; pos -= pos&-pos) ans += tree[pos];
        return ans;
    }
};

vector<vector<int>> adj(N, vector<int>());
vector<int> to(N), tin(N), sz(N, 1);

int timer = 1;
void dfs(int cur, int prev){
    tin[cur] = timer++;
    for(int child : adj[cur]){
        if(child == prev) continue;
        dfs(child, cur);
        sz[cur] += sz[child];
    }
}

int main(){
    
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    
    // ifstream cin();
    // ofstream cout();
    
    int n, r, q, reg[N];
    cin >> n >> r >> q >> reg[1];

    vector<vector<int>> region(r+1, vector<int>());
    region[reg[1]].PB(1);

    for(int i = 2; i <= n; i++){
        cin >> to[i] >> reg[i];
        region[reg[i]].PB(i);
        adj[i].PB(to[i]);
        adj[to[i]].PB(i);
    }

    dfs(1, -1);

    vector<BIT> bit(r+1, BIT(n));

    // O(nlogn) pre-build fenwick tree
    for(int i = 1; i <= n; i++){
        bit[reg[i]].add(tin[i], 1);
        bit[reg[i]].add(tin[i] + sz[i], -1);
    }

    while(q--){
        int r1, r2;
        cin >> r1 >> r2;

        // O(max(r2)logn) = O(nlogn) query... too slow
        // Search for how many ancestor with region r above a person i can be achieved in O(logn)

        ll num = 0;
        for(int i : region[r2]){
            num += bit[r1].sum(tin[i]);
        }

        cout << num << endl;
    }

}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 8280 KB Output is correct
2 Correct 3 ms 8280 KB Output is correct
3 Correct 5 ms 8304 KB Output is correct
4 Correct 4 ms 8336 KB Output is correct
5 Correct 6 ms 8420 KB Output is correct
6 Correct 12 ms 9192 KB Output is correct
7 Correct 16 ms 9264 KB Output is correct
8 Correct 16 ms 9980 KB Output is correct
9 Correct 35 ms 14732 KB Output is correct
10 Correct 59 ms 25220 KB Output is correct
11 Correct 84 ms 24868 KB Output is correct
12 Correct 107 ms 44720 KB Output is correct
13 Correct 129 ms 41388 KB Output is correct
14 Correct 213 ms 33356 KB Output is correct
15 Correct 254 ms 50948 KB Output is correct

Subtask #2
15.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 4864 ms 71672 KB Output is correct
2 Correct 7311 ms 81736 KB Output is correct
3 Correct 7033 ms 105996 KB Output is correct
4 Runtime error 71 ms 131072 KB Execution killed with signal 9
5 Runtime error 54 ms 131072 KB Execution killed with signal 9
6 Runtime error 62 ms 131072 KB Execution killed with signal 9
7 Runtime error 65 ms 131072 KB Execution killed with signal 9
8 Runtime error 69 ms 131072 KB Execution killed with signal 9
9 Runtime error 81 ms 131072 KB Execution killed with signal 9
10 Runtime error 93 ms 131072 KB Execution killed with signal 9
11 Runtime error 106 ms 131072 KB Execution killed with signal 9
12 Runtime error 102 ms 131072 KB Execution killed with signal 9
13 Runtime error 99 ms 131072 KB Execution killed with signal 9
14 Runtime error 104 ms 131072 KB Execution killed with signal 9
15 Runtime error 102 ms 131072 KB Execution killed with signal 9
16 Runtime error 97 ms 131072 KB Execution killed with signal 9
17 Runtime error 90 ms 131072 KB Execution killed with signal 9