oj.uz

Submission #1001111

# Submission time Handle Problem Language Result Execution time Memory
1001111 2024-06-18T14:49:27 Z kh0i Regions (IOI09_regions) C++17
100 / 100
 2935 ms 57780 KB 
#include "bits/stdc++.h"
using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...)
#endif

using ll = long long;
using pii = pair<int, int>;

#define F first
#define S second
#define sz(x) (int)((x).size())
#define all(x) (x).begin(), (x).end()

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll get_rand(ll l, ll r) {
    assert(l <= r);
    return uniform_int_distribution<ll> (l, r)(rng);
}

const int N = 2e5 + 3;
const int R = 25003;
const int B = 500;

int n, r, q, h[N], id[N], d[N * 2];
vector<int> g[N], dak[N], big;
int tin[N], tout[N], et[N * 2], timer;

int ansb1[N / B + 2][R], ansb2[N / B + 2][R];
vector<pii> e[N], sus;

void dfs(int u, int pre = -1){
    tin[u] = ++timer;
    et[timer] = u;
    dak[h[u]].push_back(u);
    e[h[u]].push_back({tin[u], 1});
    sus.push_back({tin[u], 1});

    for(int v : g[u])
        if(v != pre)
            dfs(v, u);

    tout[u] = ++timer;
    et[timer] = u;
    e[h[u]].push_back({tout[u], -1});
    sus.push_back({tout[u], -1});
}

void solve(){
    cin >> n >> r >> q;
    cin >> h[1];
    for(int i = 2; i <= n; ++i){
        int p;
        cin >> p >> h[i];
        g[p].push_back(i);
    }
    dfs(1);
    memset(id, -1, sizeof(id));
    for(int i = 1; i <= r; ++i){
        sort(all(e[i]));
        if(sz(dak[i]) >= B){
            id[i] = sz(big);
            big.push_back(i);
        }
    }

    sort(all(sus));

    // precalc
    // big - ?
    for(int r1 : big){
        ll cnt = 0;
        for(auto [x, y] : sus){
            if(h[et[x]] == r1)
                cnt += y;
            else{
                if(y == -1)
                    continue;
                ansb1[id[r1]][h[et[x]]] += cnt;
            }
        }
    }

    // ? - big
    for(int r1 : big){
        for(auto [x, y] : e[r1])
            if(y != -1)
                ++d[x];
        for(int i = 1; i <= timer; ++i)
            d[i] += d[i - 1];

        for(int r2 = 1; r2 <= r; ++r2){
            if(r1 == r2)
                continue;
            for(int u : dak[r2])
                ansb2[id[r1]][r2] += d[tout[u]] - d[tin[u] - 1];
        }

        for(int i = 1; i <= timer; ++i)
            d[i] = 0;
    }

    while(q--){
        int r1, r2;
        cin >> r1 >> r2;
        if(id[r1] != -1)
            cout << ansb1[id[r1]][r2] << endl;
        else if(id[r2] != -1)
            cout << ansb2[id[r2]][r1] << endl;
        else{
            int res = 0;
            vector<pii> x(sz(e[r1]) + sz(e[r2]));
            merge(all(e[r1]), all(e[r2]), x.begin());
            //debug(r1, r2, x);
            int cur = 0;
            for(auto [x, y] : x){
                if(h[et[x]] == r2)
                    res += (y == -1 ? 0 : cur);
                else
                    cur += y;
            }

            cout << res << endl;
        }
    }
}

int32_t main() {
    cin.tie(nullptr)->sync_with_stdio(0);
    #define task "troll"
    if(fopen(task".inp", "r")){
        freopen(task".inp", "r", stdin);
        freopen(task".out", "w", stdout);
    }
    int test = 1;
//    cin >> test;
    for(int i = 1; i <= test; ++i){
//        cout << "Case #" << i << ": ";
        solve();
    }
    #ifdef LOCAL
        cerr << "\n[Time]: " << 1000.0 * clock() / CLOCKS_PER_SEC << " ms.\n";
    #endif
    return 0;
}

Compilation message

regions.cpp: In function 'int32_t main()':
regions.cpp:135:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  135 |         freopen(task".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
regions.cpp:136:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  136 |         freopen(task".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 21332 KB Output is correct
2 Correct 3 ms 21080 KB Output is correct
3 Correct 4 ms 21080 KB Output is correct
4 Correct 5 ms 21080 KB Output is correct
5 Correct 8 ms 21336 KB Output is correct
6 Correct 12 ms 21320 KB Output is correct
7 Correct 19 ms 21080 KB Output is correct
8 Correct 19 ms 21336 KB Output is correct
9 Correct 29 ms 22104 KB Output is correct
10 Correct 55 ms 21972 KB Output is correct
11 Correct 95 ms 22484 KB Output is correct
12 Correct 104 ms 23252 KB Output is correct
13 Correct 116 ms 22992 KB Output is correct
14 Correct 173 ms 23760 KB Output is correct
15 Correct 260 ms 28624 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 893 ms 30664 KB Output is correct
2 Correct 871 ms 28868 KB Output is correct
3 Correct 1801 ms 33724 KB Output is correct
4 Correct 195 ms 23760 KB Output is correct
5 Correct 267 ms 27084 KB Output is correct
6 Correct 627 ms 29892 KB Output is correct
7 Correct 1043 ms 28108 KB Output is correct
8 Correct 884 ms 37700 KB Output is correct
9 Correct 1498 ms 38848 KB Output is correct
10 Correct 2935 ms 45504 KB Output is correct
11 Correct 2657 ms 36388 KB Output is correct
12 Correct 887 ms 38836 KB Output is correct
13 Correct 1304 ms 39868 KB Output is correct
14 Correct 1433 ms 42420 KB Output is correct
15 Correct 2071 ms 46776 KB Output is correct
16 Correct 2480 ms 57020 KB Output is correct
17 Correct 2161 ms 57780 KB Output is correct