oj.uz

Submission #1037275

# Submission time Handle Problem Language Result Execution time Memory
1037275 2024-07-28T12:19:56 Z Br3ad Regions (IOI09_regions) C++17
55 / 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((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
    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 {
            vector<pair<int, int>> v;
            for(int i : reg_member[r2]) v.PB(MP(tin[i], 0));
            for(int i : reg_member[r1]){
                v.PB(MP(tin[i], 1));
                v.PB(MP(tout[i], -1));
            }

            sort(v.begin(), v.end());

            int ans = 0, cur = 0;
            for(auto [_, num] : v){
                cur += num;
                if(!num) ans += cur;
            }
 
            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 4 ms 7544 KB Output is correct
4 Correct 4 ms 7512 KB Output is correct
5 Correct 6 ms 7556 KB Output is correct
6 Correct 11 ms 7512 KB Output is correct
7 Correct 18 ms 7512 KB Output is correct
8 Correct 29 ms 7512 KB Output is correct
9 Correct 39 ms 7916 KB Output is correct
10 Correct 64 ms 7940 KB Output is correct
11 Correct 123 ms 8024 KB Output is correct
12 Correct 134 ms 8784 KB Output is correct
13 Correct 205 ms 8280 KB Output is correct
14 Correct 378 ms 9504 KB Output is correct
15 Correct 393 ms 11424 KB Output is correct

Subtask #2
40.0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 8085 ms 18472 KB Time limit exceeded
2 Execution timed out 8021 ms 14620 KB Time limit exceeded
3 Execution timed out 8025 ms 16880 KB Time limit exceeded
4 Correct 287 ms 9044 KB Output is correct
5 Correct 305 ms 10144 KB Output is correct
6 Correct 511 ms 22660 KB Output is correct
7 Correct 1420 ms 24924 KB Output is correct
8 Correct 1172 ms 55296 KB Output is correct
9 Correct 3012 ms 15280 KB Output is correct
10 Correct 3122 ms 87668 KB Output is correct
11 Correct 5107 ms 15124 KB Output is correct
12 Execution timed out 8077 ms 19048 KB Time limit exceeded
13 Execution timed out 8007 ms 18968 KB Time limit exceeded
14 Execution timed out 8004 ms 34368 KB Time limit exceeded
15 Execution timed out 8063 ms 23104 KB Time limit exceeded
16 Execution timed out 8026 ms 28716 KB Time limit exceeded
17 Execution timed out 8090 ms 43636 KB Time limit exceeded