oj.uz

Submission #961190

# Submission time Handle Problem Language Result Execution time Memory
961190 2024-04-11T16:28:43 Z steveonalex Regions (IOI09_regions) C++17
74 / 100
 3444 ms 48100 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{
            // printArr(in[r1]); printArr(out[r1]);
            // printArr(in[r2]); printArr(out[r2]); 
            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 4 ms 16728 KB Output is correct
2 Correct 4 ms 16728 KB Output is correct
3 Correct 6 ms 16984 KB Output is correct
4 Correct 7 ms 16904 KB Output is correct
5 Correct 8 ms 17188 KB Output is correct
6 Correct 15 ms 17488 KB Output is correct
7 Correct 18 ms 17756 KB Output is correct
8 Correct 23 ms 17520 KB Output is correct
9 Correct 38 ms 18816 KB Output is correct
10 Correct 67 ms 18504 KB Output is correct
11 Correct 88 ms 19048 KB Output is correct
12 Correct 106 ms 19492 KB Output is correct
13 Correct 124 ms 19296 KB Output is correct
14 Correct 199 ms 19536 KB Output is correct
15 Runtime error 198 ms 22432 KB Execution killed with signal 13

Subtask #2
60.0 / 85.0

# Verdict Execution time Memory Grader output
1 Runtime error 884 ms 23544 KB Execution killed with signal 13
2 Correct 1064 ms 22036 KB Output is correct
3 Correct 1477 ms 27336 KB Output is correct
4 Correct 181 ms 20332 KB Output is correct
5 Correct 275 ms 23204 KB Output is correct
6 Correct 379 ms 22104 KB Output is correct
7 Correct 597 ms 21864 KB Output is correct
8 Correct 790 ms 29576 KB Output is correct
9 Correct 1578 ms 33792 KB Output is correct
10 Correct 2857 ms 40112 KB Output is correct
11 Runtime error 3444 ms 37096 KB Execution killed with signal 13
12 Runtime error 1118 ms 31344 KB Execution killed with signal 13
13 Runtime error 1534 ms 34036 KB Execution killed with signal 13
14 Runtime error 1893 ms 35024 KB Execution killed with signal 13
15 Correct 2410 ms 41452 KB Output is correct
16 Correct 2357 ms 48100 KB Output is correct
17 Correct 2421 ms 46024 KB Output is correct