oj.uz

Submission #961201

# Submission time Handle Problem Language Result Execution time Memory
961201 2024-04-11T16:47:36 Z steveonalex Regions (IOI09_regions) C++17
44 / 100
 3445 ms 91180 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, BLOCK = 500;

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];
vector<int> sum_in[N], sum_out[N];

int pro_count_1(int r1, int r2){
    int ans = 0;
    for(int i: in[r1]){
        ans -= sum_in[r2][i-1];
    }
    for(int i: out[r1]){
        ans += sum_out[r2][i];
    }
    return ans;
}
int pro_count_2(int r1, int r2){
    int ans = 0;
    for(int i: in[r2]){
        ans -= sum_out[r1][i-1] - sum_in[r1][i];
    }
    return ans;
}

int suck_count_1(int r1, int r2){
    int ans = 0;
    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();
    }
    return ans;
}

int suck_count_2(int r1, int r2){
    int ans = 0;
    for(int i: in[r2]){
        ans -= (lower_bound(ALL(out[r1]), i) - out[r1].begin()) - (upper_bound(ALL(in[r1]), i) - in[r1].begin());
    }
    return ans;
}

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]));
    }

    for(int i= 1; i<=R; ++i) if (in[i].size() > BLOCK) {
        sum_in[i].resize(n+1), sum_out[i].resize(n+1);
        for(int j: in[i]) sum_in[i][j]++;
        for(int j: out[i]) sum_out[i][j]++;
        for(int j = 1; j<=n; ++j) {
            sum_in[i][j] += sum_in[i][j-1];
            sum_out[i][j] += sum_out[i][j-1];
        }
    }

    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()){
            if (in[r2].size() > BLOCK) ans = pro_count_1(r1, r2);
            else ans = suck_count_1(r1, r2);
        }
        else{
            if (in[r1].size() > BLOCK) ans = pro_count_2(r1, r2);
            else ans = suck_count_2(r1, r2);
        }
        cout << ans << endl << endl;
        mp[cur] = ans;
    }

    return 0;
}

Subtask #1
14.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 26200 KB Output is correct
2 Correct 6 ms 26088 KB Output is correct
3 Correct 6 ms 26300 KB Output is correct
4 Correct 9 ms 26812 KB Output is correct
5 Correct 10 ms 26584 KB Output is correct
6 Correct 14 ms 26716 KB Output is correct
7 Correct 24 ms 27480 KB Output is correct
8 Correct 24 ms 27688 KB Output is correct
9 Correct 45 ms 27620 KB Output is correct
10 Correct 58 ms 27944 KB Output is correct
11 Correct 83 ms 28456 KB Output is correct
12 Correct 108 ms 29144 KB Output is correct
13 Correct 128 ms 29020 KB Output is correct
14 Correct 199 ms 28668 KB Output is correct
15 Runtime error 197 ms 31624 KB Execution killed with signal 13

Subtask #2
30.0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 813 ms 39652 KB Output isn't correct
2 Incorrect 934 ms 39976 KB Output isn't correct
3 Runtime error 1471 ms 43688 KB Execution killed with signal 13
4 Correct 173 ms 30336 KB Output is correct
5 Correct 246 ms 32808 KB Output is correct
6 Correct 381 ms 31872 KB Output is correct
7 Correct 560 ms 31716 KB Output is correct
8 Correct 782 ms 39408 KB Output is correct
9 Correct 1557 ms 42712 KB Output is correct
10 Runtime error 2821 ms 49312 KB Execution killed with signal 13
11 Runtime error 3445 ms 46372 KB Execution killed with signal 13
12 Incorrect 1044 ms 43316 KB Output isn't correct
13 Incorrect 1439 ms 45712 KB Output isn't correct
14 Runtime error 1577 ms 78560 KB Execution killed with signal 13
15 Incorrect 2431 ms 54188 KB Output isn't correct
16 Incorrect 2285 ms 60180 KB Output isn't correct
17 Incorrect 2214 ms 91180 KB Output isn't correct