oj.uz

Submission #984995

# Submission time Handle Problem Language Result Execution time Memory
984995 2024-05-17T09:09:39 Z Br3ad Regions (IOI09_regions) C++17
30 / 100
 7272 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 R = 25000 + 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+2), tree(n+2, 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 4 ms 8280 KB Output is correct
4 Correct 5 ms 8328 KB Output is correct
5 Correct 7 ms 8424 KB Output is correct
6 Correct 13 ms 9192 KB Output is correct
7 Correct 19 ms 9260 KB Output is correct
8 Correct 17 ms 9876 KB Output is correct
9 Correct 31 ms 14736 KB Output is correct
10 Correct 57 ms 25248 KB Output is correct
11 Correct 75 ms 24864 KB Output is correct
12 Correct 129 ms 44724 KB Output is correct
13 Correct 123 ms 41388 KB Output is correct
14 Correct 170 ms 33200 KB Output is correct
15 Correct 280 ms 50952 KB Output is correct

Subtask #2
15.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 4845 ms 71752 KB Output is correct
2 Correct 7272 ms 81880 KB Output is correct
3 Correct 7151 ms 106128 KB Output is correct
4 Runtime error 112 ms 131072 KB Execution killed with signal 9
5 Runtime error 73 ms 131072 KB Execution killed with signal 9
6 Runtime error 87 ms 131072 KB Execution killed with signal 9
7 Runtime error 113 ms 131072 KB Execution killed with signal 9
8 Runtime error 100 ms 131072 KB Execution killed with signal 9
9 Runtime error 91 ms 131072 KB Execution killed with signal 9
10 Runtime error 98 ms 131072 KB Execution killed with signal 9
11 Runtime error 111 ms 131072 KB Execution killed with signal 9
12 Runtime error 121 ms 131072 KB Execution killed with signal 9
13 Runtime error 97 ms 131072 KB Execution killed with signal 9
14 Runtime error 109 ms 131072 KB Execution killed with signal 9
15 Runtime error 108 ms 131072 KB Execution killed with signal 9
16 Runtime error 92 ms 131072 KB Execution killed with signal 9
17 Runtime error 108 ms 131072 KB Execution killed with signal 9