oj.uz

답안 #1037198

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1037198 2024-07-28T10:29:33 Z Br3ad Regions (IOI09_regions) C++17
80 / 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 {
            // 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;
        }
    }
}

Subtask #1
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 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 4 ms 7512 KB Output is correct
5 Correct 5 ms 7544 KB Output is correct
6 Correct 11 ms 7596 KB Output is correct
7 Correct 19 ms 7760 KB Output is correct
8 Correct 20 ms 7672 KB Output is correct
9 Correct 33 ms 7768 KB Output is correct
10 Correct 61 ms 8016 KB Output is correct
11 Correct 100 ms 8272 KB Output is correct
12 Correct 116 ms 8568 KB Output is correct
13 Correct 177 ms 8280 KB Output is correct
14 Correct 304 ms 9504 KB Output is correct
15 Correct 399 ms 11440 KB Output is correct

Subtask #2
65.0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3744 ms 18532 KB Output is correct
2 Correct 4049 ms 14648 KB Output is correct
3 Correct 5775 ms 17040 KB Output is correct
4 Correct 306 ms 8900 KB Output is correct
5 Correct 360 ms 10136 KB Output is correct
6 Correct 472 ms 22476 KB Output is correct
7 Correct 1211 ms 24920 KB Output is correct
8 Correct 1231 ms 55164 KB Output is correct
9 Correct 3422 ms 15268 KB Output is correct
10 Correct 3402 ms 87668 KB Output is correct
11 Correct 5680 ms 15108 KB Output is correct
12 Correct 6352 ms 18916 KB Output is correct
13 Correct 7517 ms 19152 KB Output is correct
14 Execution timed out 8034 ms 34424 KB Time limit exceeded
15 Execution timed out 8084 ms 23212 KB Time limit exceeded
16 Execution timed out 8087 ms 28480 KB Time limit exceeded
17 Execution timed out 8063 ms 43700 KB Time limit exceeded