oj.uz

Submission #961207

# Submission time Handle Problem Language Result Execution time Memory
961207 2024-04-11T16:56:10 Z steveonalex Regions (IOI09_regions) C++17
100 / 100
 3107 ms 47516 KB 
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
 
#define ALL(v) (v).begin(), (v).end()
#define MASK(i) (1LL << (i))
#define GETBIT(mask, i) (((mask) >> (i)) & 1)
 
// mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
mt19937_64 rng(1);
ll rngesus(ll l, ll r){return ((ull) rng()) % (r - l + 1) + l;}
 
ll max(ll a, ll b){return (a > b) ? a : b;}
ll min(ll a, ll b){return (a < b) ? a : b;}
 
ll LASTBIT(ll mask){return mask & (-mask);}
ll pop_cnt(ll mask){return __builtin_popcountll(mask);}
ll ctz(ll mask){return __builtin_ctzll(mask);}
ll clz(ll mask){return __builtin_clzll(mask);}
ll logOf(ll mask){return 63 - clz(mask);}
 
template <class T1, class T2>
    bool minimize(T1 &a, T2 b){
        if (a > b){a = b; return true;}
        return false;
    }
template <class T1, class T2>
    bool maximize(T1 &a, T2 b){
        if (a < b){a = b; return true;}
        return false;
    }
template <class T>
    void printArr(T& a, string separator = " ", string finish = "\n"){
        for(auto i: a) cout << i << separator;
        cout << finish;
    }
template <class T>
    void remove_dup(vector<T> &a){
        sort(ALL(a));
        a.resize(unique(ALL(a)) - a.begin());
    }
 
const int N = 2e5 + 69;
 
int n, R, q;
vector<int> graph[N];
int region[N];
 
int l[N], r[N];
int dfs_cnt = 0;
 
void dfs(int u){
    l[u] = r[u] = ++dfs_cnt;
    for(int v: graph[u]){
        dfs(v);
        r[u] = r[v];
    }
}
 
vector<int> in[N], out[N];
 
int main(void){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
 
    cin >> n >> R >> q;
    cin >> region[1];
    for(int i = 2; i<=n; ++i){
        int j;
        cin >> j >> region[i];
 
        graph[j].push_back(i);
    }
 
    dfs(1);
 
    for(int i= 1; i<=n; ++i){
        in[region[i]].push_back(l[i]);
        out[region[i]].push_back(r[i]);
    }
 
    for(int i = 1; i<=R; ++i){
        sort(ALL(in[i]));
        sort(ALL(out[i]));
    }

 
    map<pair<int, int>, int> mp;
    while(q--){
        int r1, r2; cin >> r1 >> r2;
        pair<int, int> cur = {r1, r2};
        if (mp.count(cur)) {cout << mp[cur] << endl; continue;}
 
        ll ans = 0;
        if (in[r1].size() <= in[r2].size()){
            for(int i: in[r1]) {
                ans -= lower_bound(ALL(in[r2]), i) - in[r2].begin();
            }
            for(int i: out[r1]) {
                ans += upper_bound(ALL(in[r2]), i) - in[r2].begin();
            }
        }
        else{
            for(int i: in[r2]){
                ans -= (lower_bound(ALL(out[r1]), i) - out[r1].begin()) - (upper_bound(ALL(in[r1]), i) - in[r1].begin());
            }
        }
        cout << ans << endl;
        mp[cur] = ans;
    }
 
    return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 16728 KB Output is correct
2 Correct 4 ms 16728 KB Output is correct
3 Correct 4 ms 16904 KB Output is correct
4 Correct 6 ms 16912 KB Output is correct
5 Correct 7 ms 17184 KB Output is correct
6 Correct 15 ms 17496 KB Output is correct
7 Correct 16 ms 18028 KB Output is correct
8 Correct 23 ms 17580 KB Output is correct
9 Correct 42 ms 18440 KB Output is correct
10 Correct 47 ms 18800 KB Output is correct
11 Correct 75 ms 18616 KB Output is correct
12 Correct 88 ms 19356 KB Output is correct
13 Correct 133 ms 19592 KB Output is correct
14 Correct 187 ms 19592 KB Output is correct
15 Correct 191 ms 22332 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 775 ms 23544 KB Output is correct
2 Correct 851 ms 22128 KB Output is correct
3 Correct 1300 ms 27348 KB Output is correct
4 Correct 152 ms 20204 KB Output is correct
5 Correct 255 ms 22452 KB Output is correct
6 Correct 347 ms 21752 KB Output is correct
7 Correct 519 ms 22408 KB Output is correct
8 Correct 734 ms 29384 KB Output is correct
9 Correct 1370 ms 33416 KB Output is correct
10 Correct 2578 ms 40316 KB Output is correct
11 Correct 3107 ms 36724 KB Output is correct
12 Correct 997 ms 31080 KB Output is correct
13 Correct 1374 ms 33188 KB Output is correct
14 Correct 1689 ms 34808 KB Output is correct
15 Correct 2141 ms 42508 KB Output is correct
16 Correct 2082 ms 47516 KB Output is correct
17 Correct 2015 ms 45252 KB Output is correct