oj.uz

Submission #525636

# Submission time Handle Problem Language Result Execution time Memory
525636 2022-02-12T08:40:43 Z Aldas25 Regions (IOI09_regions) C++14
30 / 100
 1412 ms 131076 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 = 0;

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 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;

        cout << ans[regToId[r1]][r2] << endl;
    }

    return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 12104 KB Output is correct
2 Correct 7 ms 12104 KB Output is correct
3 Correct 9 ms 12104 KB Output is correct
4 Correct 11 ms 12232 KB Output is correct
5 Correct 13 ms 12356 KB Output is correct
6 Correct 28 ms 13640 KB Output is correct
7 Correct 35 ms 13000 KB Output is correct
8 Correct 34 ms 13384 KB Output is correct
9 Correct 65 ms 14544 KB Output is correct
10 Correct 101 ms 16064 KB Output is correct
11 Correct 116 ms 14856 KB Output is correct
12 Correct 165 ms 17208 KB Output is correct
13 Correct 218 ms 15824 KB Output is correct
14 Correct 177 ms 15440 KB Output is correct
15 Correct 257 ms 17592 KB Output is correct

Subtask #2
15.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 894 ms 18760 KB Output is correct
2 Correct 715 ms 18100 KB Output is correct
3 Correct 1374 ms 20908 KB Output is correct
4 Runtime error 186 ms 64660 KB Execution killed with signal 11
5 Runtime error 212 ms 75036 KB Execution killed with signal 11
6 Runtime error 300 ms 91604 KB Execution killed with signal 11
7 Runtime error 404 ms 117872 KB Execution killed with signal 11
8 Runtime error 513 ms 125984 KB Execution killed with signal 11
9 Runtime error 800 ms 131072 KB Execution killed with signal 11
10 Runtime error 941 ms 131072 KB Execution killed with signal 11
11 Runtime error 1260 ms 131072 KB Execution killed with signal 11
12 Runtime error 1412 ms 131072 KB Execution killed with signal 11
13 Runtime error 918 ms 90048 KB Execution killed with signal 13
14 Runtime error 1375 ms 131072 KB Execution killed with signal 11
15 Runtime error 1058 ms 131072 KB Execution killed with signal 11
16 Runtime error 925 ms 131076 KB Execution killed with signal 9
17 Runtime error 1108 ms 131072 KB Execution killed with signal 11