oj.uz

Submission #1037193

# Submission time Handle Problem Language Result Execution time Memory
1037193 2024-07-28T10:18:55 Z Br3ad Regions (IOI09_regions) C++17
20 / 100
 3232 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 query(int pos){
        int ans = 0;
        for(; pos >= 1; pos -= pos&-pos) ans += tree[pos];
        return ans;
    }
};

vector<vector<int>> adj(N, vector<int>()), pre;
vector<int> reg(N), tin(N), tout(N);

void pre_dfs(int par_reg, int par_cnt, int cur, vector<int> &pre_temp){
    if(par_reg != reg[cur]) pre_temp[reg[cur]] += par_cnt;
    for(int child : adj[cur]){
        pre_dfs(par_reg, par_cnt + (par_reg == reg[child]), child, pre_temp);
    }
}

int timer = 1;
void get_euler(int cur){
    tin[cur] = timer++;
    for(int child : adj[cur]) get_euler(child);
    tout[cur] = timer++;
}

int main(){
    
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    
    // ifstream cin();
    // ofstream cout();
    
    int n, r, q;
    cin >> n >> r >> q;
    
    cin >> reg[1];
    for(int i = 2; i <= n; i++){
        int par;
        cin >> par >> reg[i];
        adj[par].PB(i);
    }
    
    // Precalculate
    vector<vector<int>> reg_member(r + 1, vector<int>());
    for(int i = 1; i <= n; i++){
        reg_member[reg[i]].PB(i);
    }

    int thres = sqrt(n);
    vector<int> precal(r + 1, -1);
    for(int i = 1; i <= r; i++){
        if((int)reg_member[i].size() > thres){
            vector<int> pre_temp(n+1, 0);
            pre_dfs(i, (reg[1] == i), 1, pre_temp);
            pre.PB(pre_temp);
            precal[i] = (int)pre.size() - 1;
        }
    }

    // Euler tour
    get_euler(1);

    vector<BIT> vbit;
    for(int i = 1; i <= r; i++){
        if(precal[i] == -1){
            BIT bit(2*n);
            for(int j : reg_member[i]){
                bit.add(tin[j], 1);
                bit.add(tout[j], -1);
            }
            vbit.PB(bit);
            precal[i] = r + (int)vbit.size() - 1;
        }
    }

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

        if(precal[r1] < r){
            cout << pre[precal[r1]][r2] << endl;
        }else {
            // Query
            int ans = 0;
            for(int mem : reg_member[r2]){
                ans += vbit[precal[r1] - r].query(tin[mem]);
            }
            cout << ans << endl;
        }
    }
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7512 KB Output is correct
2 Correct 2 ms 7512 KB Output is correct
3 Correct 3 ms 7512 KB Output is correct
4 Correct 3 ms 7512 KB Output is correct
5 Correct 5 ms 7512 KB Output is correct
6 Correct 12 ms 9172 KB Output is correct
7 Correct 24 ms 9304 KB Output is correct
8 Correct 18 ms 10840 KB Output is correct
9 Correct 26 ms 19696 KB Output is correct
10 Correct 69 ms 40792 KB Output is correct
11 Correct 87 ms 40016 KB Output is correct
12 Correct 124 ms 79024 KB Output is correct
13 Correct 159 ms 72084 KB Output is correct
14 Correct 183 ms 55396 KB Output is correct
15 Correct 230 ms 86140 KB Output is correct

Subtask #2
5.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 3232 ms 122260 KB Output is correct
2 Runtime error 92 ms 131072 KB Execution killed with signal 9
3 Runtime error 91 ms 131072 KB Execution killed with signal 9
4 Runtime error 59 ms 131072 KB Execution killed with signal 9
5 Runtime error 64 ms 131072 KB Execution killed with signal 9
6 Runtime error 125 ms 131072 KB Execution killed with signal 9
7 Runtime error 143 ms 131072 KB Execution killed with signal 9
8 Runtime error 137 ms 131072 KB Execution killed with signal 9
9 Runtime error 83 ms 131072 KB Execution killed with signal 9
10 Runtime error 204 ms 131072 KB Execution killed with signal 9
11 Runtime error 88 ms 131072 KB Execution killed with signal 9
12 Runtime error 105 ms 131072 KB Execution killed with signal 9
13 Runtime error 96 ms 131072 KB Execution killed with signal 9
14 Runtime error 224 ms 131072 KB Execution killed with signal 9
15 Runtime error 87 ms 131072 KB Execution killed with signal 9
16 Runtime error 89 ms 131072 KB Execution killed with signal 9
17 Runtime error 115 ms 131072 KB Execution killed with signal 9