oj.uz

Submission #1037280

# Submission time Handle Problem Language Result Execution time Memory
1037280 2024-07-28T12:37:39 Z Br3ad Regions (IOI09_regions) C++17
100 / 100
 3317 ms 87708 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;
 
vector<vector<int>> adj(N, vector<int>()), reg_tour(R, 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++;
    reg_tour[reg[cur]].PB(tin[cur]);
    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);
 
    while(q--){
        int r1, r2;
        cin >> r1 >> r2;
 
        if(precal[r1] != -1){
            cout << pre[precal[r1]][r2] << endl;
        }else {
            int ans = 0;
            for(int i : reg_member[r1]){
                ans += lower_bound(reg_tour[r2].begin(), reg_tour[r2].end(), tout[i]) - lower_bound(reg_tour[r2].begin(), reg_tour[r2].end(), tin[i]);
            }
 
            cout << ans << endl;
        }
    }
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 8024 KB Output is correct
2 Correct 3 ms 7992 KB Output is correct
3 Correct 3 ms 8108 KB Output is correct
4 Correct 4 ms 8024 KB Output is correct
5 Correct 6 ms 8024 KB Output is correct
6 Correct 10 ms 8024 KB Output is correct
7 Correct 15 ms 8156 KB Output is correct
8 Correct 17 ms 8184 KB Output is correct
9 Correct 29 ms 8484 KB Output is correct
10 Correct 51 ms 8784 KB Output is correct
11 Correct 74 ms 8740 KB Output is correct
12 Correct 93 ms 9296 KB Output is correct
13 Correct 126 ms 8844 KB Output is correct
14 Correct 192 ms 9816 KB Output is correct
15 Correct 189 ms 11960 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1403 ms 18620 KB Output is correct
2 Correct 1701 ms 14864 KB Output is correct
3 Correct 2289 ms 17008 KB Output is correct
4 Correct 215 ms 9512 KB Output is correct
5 Correct 271 ms 10680 KB Output is correct
6 Correct 429 ms 22796 KB Output is correct
7 Correct 908 ms 25232 KB Output is correct
8 Correct 785 ms 55288 KB Output is correct
9 Correct 1839 ms 15892 KB Output is correct
10 Correct 2316 ms 87708 KB Output is correct
11 Correct 3317 ms 15856 KB Output is correct
12 Correct 1052 ms 18444 KB Output is correct
13 Correct 1454 ms 18640 KB Output is correct
14 Correct 1733 ms 34252 KB Output is correct
15 Correct 2495 ms 23104 KB Output is correct
16 Correct 2217 ms 28400 KB Output is correct
17 Correct 2091 ms 43488 KB Output is correct