oj.uz

Submission #961202

# Submission time Handle Problem Language Result Execution time Memory
961202 2024-04-11T16:51:11 Z steveonalex Regions (IOI09_regions) C++17
64 / 100
 3382 ms 47840 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]));
    }
 
    cout << endl;
 
    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 << 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 << endl;
        mp[cur] = ans;
    }
 
    return 0;
}

Subtask #1
14.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 16728 KB Output is correct
2 Correct 4 ms 16728 KB Output is correct
3 Correct 5 ms 16900 KB Output is correct
4 Correct 5 ms 17164 KB Output is correct
5 Correct 9 ms 17440 KB Output is correct
6 Correct 14 ms 18544 KB Output is correct
7 Correct 22 ms 17276 KB Output is correct
8 Correct 21 ms 17548 KB Output is correct
9 Correct 33 ms 18716 KB Output is correct
10 Correct 66 ms 17784 KB Output is correct
11 Correct 92 ms 18940 KB Output is correct
12 Correct 101 ms 19640 KB Output is correct
13 Correct 136 ms 19460 KB Output is correct
14 Correct 202 ms 20064 KB Output is correct
15 Runtime error 204 ms 23160 KB Execution killed with signal 13

Subtask #2
50.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 909 ms 23228 KB Output is correct
2 Runtime error 1051 ms 22240 KB Execution killed with signal 13
3 Correct 1477 ms 27364 KB Output is correct
4 Runtime error 160 ms 20924 KB Execution killed with signal 13
5 Runtime error 244 ms 23200 KB Execution killed with signal 13
6 Correct 359 ms 22528 KB Output is correct
7 Correct 557 ms 22716 KB Output is correct
8 Correct 762 ms 29864 KB Output is correct
9 Correct 1553 ms 33792 KB Output is correct
10 Runtime error 2911 ms 40360 KB Execution killed with signal 13
11 Correct 3382 ms 36352 KB Output is correct
12 Runtime error 1125 ms 31932 KB Execution killed with signal 13
13 Correct 1542 ms 33440 KB Output is correct
14 Runtime error 1875 ms 34152 KB Execution killed with signal 13
15 Runtime error 2429 ms 42060 KB Execution killed with signal 13
16 Correct 2435 ms 47840 KB Output is correct
17 Correct 2347 ms 46116 KB Output is correct