oj.uz

Submission #525628

# Submission time Handle Problem Language Result Execution time Memory
525628 2022-02-12T07:59:53 Z Aldas25 Regions (IOI09_regions) C++14
29 / 100
 1274 ms 31792 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];
ll pref[25100];
int regToId[MAXN];
int idToReg[MAXN];
int tin[MAXN], tout[MAXN];
int crT = 0;

ll ans1[C][25100];
ll ans2[C][25100];

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

    FOR(i, 0, C-1) {
        ans1[i][h[v]] += pref[idToReg[i]];
        //ans2[i][h[v]] += pref[h[v]];
    }

    if (bgReg[h[v]]) {
        FOR(i, 1, r)
            ans2[regToId[h[v]]][i] += pref[i];
    }

    pref[h[v]]++;

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

    pref[h[v]]--;

    tout[v] = crT;
}

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


ll r1Big (int r1, int r2) {
    return ans1[regToId[r1]][r2];
}

ll r2Big (int r1, int r2) {
    return ans2[regToId[r2]][r1];
}

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

    REP(q) {
        int r1, r2;
        cin >> r1 >> r2;
        if(bgReg[r1])
            cout << r1Big(r1, r2) << endl;
        else if (bgReg[r2])
            cout << r2Big(r1, r2) << endl;
    }

    return 0;
}

Subtask #1
14.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8368 KB Output is correct
2 Correct 5 ms 8392 KB Output is correct
3 Correct 6 ms 8520 KB Output is correct
4 Correct 7 ms 8648 KB Output is correct
5 Correct 10 ms 8756 KB Output is correct
6 Execution timed out 16 ms 10952 KB Time limit exceeded (wall clock)
7 Correct 38 ms 9776 KB Output is correct
8 Correct 39 ms 10440 KB Output is correct
9 Correct 54 ms 12120 KB Output is correct
10 Correct 71 ms 13696 KB Output is correct
11 Correct 91 ms 11848 KB Output is correct
12 Correct 125 ms 14868 KB Output is correct
13 Correct 184 ms 12728 KB Output is correct
14 Correct 148 ms 11464 KB Output is correct
15 Correct 159 ms 15036 KB Output is correct

Subtask #2
15.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 684 ms 14400 KB Output is correct
2 Correct 950 ms 13120 KB Output is correct
3 Correct 1274 ms 17120 KB Output is correct
4 Runtime error 32 ms 18636 KB Execution killed with signal 11
5 Runtime error 42 ms 27944 KB Execution killed with signal 11
6 Runtime error 39 ms 24264 KB Execution killed with signal 11
7 Runtime error 35 ms 21372 KB Execution killed with signal 11
8 Runtime error 49 ms 24232 KB Execution killed with signal 11
9 Runtime error 54 ms 27136 KB Execution killed with signal 11
10 Runtime error 68 ms 29600 KB Execution killed with signal 11
11 Runtime error 94 ms 30704 KB Execution killed with signal 11
12 Runtime error 77 ms 30692 KB Execution killed with signal 11
13 Runtime error 65 ms 29544 KB Execution killed with signal 11
14 Runtime error 66 ms 29432 KB Execution killed with signal 11
15 Runtime error 71 ms 31768 KB Execution killed with signal 11
16 Runtime error 68 ms 31792 KB Execution killed with signal 11
17 Runtime error 68 ms 31612 KB Execution killed with signal 11