oj.uz

Submission #525643

# Submission time Handle Problem Language Result Execution time Memory
525643 2022-02-12T08:49:31 Z Aldas25 Regions (IOI09_regions) C++14
30 / 100
 1497 ms 131080 KB 
#include <bits/stdc++.h>

using namespace std;

#define FAST_IO ios_base::sync_with_stdio(0); cin.tie(0)
#define FOR(i, a, b) for(int i = (a); i <= (b); i++)
#define REP(n) FOR(O, 1, (n))
#define pb push_back
#define f first
#define s second
typedef long double ld;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pii> vii;
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int MAXN = 250100, MAXK = 20;
const ll MOD = 1e9+7;

const ll C = 500;
const ll c = 2;

int n, r, q;
int h[MAXN];
int regSz[MAXN];
bool bgReg[MAXN];
vi adj[MAXN];

int regToId[MAXN];
int idToReg[MAXN];

int tin[MAXN], tout[MAXN];
int crT = 0;

void dfs (int v, int p = -1) {
    tin[v] = ++crT;

    for (int u : adj[v]) {
        dfs (u, v);
    }

    tout[v] = crT;
}

bool isAnc (int a, int b) {
    return (tin[a] <= tin[b] && tout[b] <= tout[a]);
}

vii nodes;
vii inReg[MAXN];
ll pref[MAXN];
ll ans[C][25100];

int getUpperBound (int r, int x) {
    int sz = (int)inReg[r].size();
    if (sz == 0) return sz;
    if (inReg[r][sz-1].f <= x) return sz;

    int le = 0, ri = sz-1;
    while (le < ri) {
        int m = (le+ri)/2;
        if (inReg[r][m].f > x) ri = m;
        else le = m+1;
    }

    return le;
}

int main()
{
    FAST_IO;

    cin >> n >> r >> q;
    cin >> h[1];
    FOR(i, 2, n) {
        int pr; cin >> pr;
        adj[pr].pb(i);
        cin >> h[i];

    }

    FOR(i, 1, n) regSz[h[i]]++;
    int lstId = 0;
    FOR(i, 1, r) {
        bgReg[i] = (regSz[i] > c);

        if (bgReg[i]) {
            regToId[i] = ++lstId;
            idToReg[lstId] = i;
        }

       // cout << " i = " << i << " regSz = " << regSz[i] << " bg = " << bgReg[i] << endl;
       // if (bgReg[i]) cout << "     regToId[i]=" << regToId[i] << endl;
    }

    dfs(1);

    FOR(i, 1, n) {
        nodes.pb({tin[i], i});
        inReg[h[i]].pb({tin[i], i});
    }

    sort(nodes.begin(), nodes.end());
    FOR(i, 1, r) sort(inReg[i].begin(), inReg[i].end());

    FOR(i, 0, C-1) {
        if (idToReg[i] == 0) continue;
        int r = idToReg[i];

        FOR(j, 0, n) pref[j] = 0;
        for (auto p : inReg[r]) {
            int v = p.s;
            pref[tin[v]]++;
            pref[tout[v]+1]--;
        }
        FOR(j, 1, n) pref[j] += pref[j-1];

        FOR(j, 1, n) {
            int v = nodes[j-1].s;
            ans[i][h[v]] += pref[j];
        }

    }

    REP(q) {
        int r1, r2;
        cin >> r1 >> r2;

        if (bgReg[r1]) {
            cout << ans[regToId[r1]][r2] << endl;
        } else {
            ll ats = 0;
            for (auto p : inReg[r1]) {
                int v = p.s;

                int ri = getUpperBound (r2, tout[v]);
                int le = getUpperBound (r2, tin[v]);

                ats += max(0, ri-le);
            }

            cout << ats << endl;
        }
    }

    return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12104 KB Output is correct
2 Correct 9 ms 12136 KB Output is correct
3 Correct 9 ms 12104 KB Output is correct
4 Correct 16 ms 12144 KB Output is correct
5 Correct 10 ms 12360 KB Output is correct
6 Correct 27 ms 13128 KB Output is correct
7 Correct 40 ms 13000 KB Output is correct
8 Correct 43 ms 13440 KB Output is correct
9 Correct 60 ms 14652 KB Output is correct
10 Correct 136 ms 16008 KB Output is correct
11 Correct 131 ms 14840 KB Output is correct
12 Correct 202 ms 17336 KB Output is correct
13 Correct 241 ms 15856 KB Output is correct
14 Correct 199 ms 15532 KB Output is correct
15 Correct 276 ms 17544 KB Output is correct

Subtask #2
15.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 886 ms 19040 KB Output is correct
2 Correct 945 ms 18080 KB Output is correct
3 Correct 1271 ms 20840 KB Output is correct
4 Runtime error 207 ms 64752 KB Execution killed with signal 11
5 Runtime error 239 ms 75068 KB Execution killed with signal 11
6 Runtime error 315 ms 91444 KB Execution killed with signal 11
7 Runtime error 436 ms 117840 KB Execution killed with signal 11
8 Runtime error 527 ms 125920 KB Execution killed with signal 11
9 Runtime error 890 ms 131072 KB Execution killed with signal 11
10 Runtime error 978 ms 131072 KB Execution killed with signal 11
11 Runtime error 1357 ms 131072 KB Execution killed with signal 11
12 Runtime error 1497 ms 131072 KB Execution killed with signal 11
13 Runtime error 1016 ms 131072 KB Execution killed with signal 11
14 Runtime error 1426 ms 131072 KB Execution killed with signal 11
15 Runtime error 1070 ms 131072 KB Execution killed with signal 11
16 Runtime error 976 ms 131080 KB Execution killed with signal 9
17 Runtime error 1186 ms 131076 KB Execution killed with signal 11