oj.uz

Submission #1037188

# Submission time Handle Problem Language Result Execution time Memory
1037188 2024-07-28T10:10:49 Z Br3ad Regions (IOI09_regions) C++17
75 / 100
 8000 ms 87668 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(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
    BIT bit(2*n);
    get_euler(1);

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

        if(precal[r1] != -1){
            cout << pre[precal[r1]][r2] << endl;
        }else {
            // Setup
            for(int mem : reg_member[r1]){
                bit.add(tin[mem], 1);
                bit.add(tout[mem], -1);
            }

            // Query
            int ans = 0;
            for(int mem : reg_member[r2]){
                ans += bit.query(tin[mem]);
            }

            // Revert
            for(int mem : reg_member[r1]){
                bit.add(tin[mem], -1);
                bit.add(tout[mem], 1);
            }

            cout << ans << endl;
        }
    }
}

Compilation message

regions.cpp: In function 'int main()':
regions.cpp:95:33: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   95 |         if(reg_member[i].size() > thres){
      |            ~~~~~~~~~~~~~~~~~~~~~^~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7512 KB Output is correct
2 Correct 2 ms 7512 KB Output is correct
3 Correct 3 ms 7440 KB Output is correct
4 Correct 4 ms 7768 KB Output is correct
5 Correct 7 ms 7540 KB Output is correct
6 Correct 14 ms 7512 KB Output is correct
7 Correct 19 ms 7592 KB Output is correct
8 Correct 19 ms 7512 KB Output is correct
9 Correct 36 ms 7908 KB Output is correct
10 Correct 57 ms 7940 KB Output is correct
11 Correct 107 ms 8188 KB Output is correct
12 Correct 113 ms 8560 KB Output is correct
13 Correct 184 ms 8280 KB Output is correct
14 Correct 325 ms 9268 KB Output is correct
15 Correct 405 ms 11408 KB Output is correct

Subtask #2
60.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 3772 ms 18536 KB Output is correct
2 Correct 4131 ms 14652 KB Output is correct
3 Correct 5889 ms 17040 KB Output is correct
4 Correct 317 ms 8908 KB Output is correct
5 Correct 359 ms 10132 KB Output is correct
6 Correct 494 ms 22476 KB Output is correct
7 Correct 1308 ms 24920 KB Output is correct
8 Correct 1198 ms 55164 KB Output is correct
9 Correct 3544 ms 15268 KB Output is correct
10 Correct 3539 ms 87668 KB Output is correct
11 Correct 5973 ms 15116 KB Output is correct
12 Correct 6923 ms 18916 KB Output is correct
13 Execution timed out 8061 ms 19104 KB Time limit exceeded
14 Execution timed out 8074 ms 34368 KB Time limit exceeded
15 Execution timed out 8068 ms 23104 KB Time limit exceeded
16 Execution timed out 8022 ms 28680 KB Time limit exceeded
17 Execution timed out 8087 ms 43840 KB Time limit exceeded