oj.uz

Submission #413440

# Submission time Handle Problem Language Result Execution time Memory
413440 2021-05-28T17:48:09 Z JerryLiu06 Regions (IOI09_regions) C++17
0 / 100
 3324 ms 31984 KB 
#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using db = long double;
using str = string;

using pi = pair<int, int>;
using pl = pair<ll, ll>;
using pd = pair<db, db>;

using vi = vector<int>;
using vb = vector<bool>;
using vl = vector<ll>;
using vd = vector<db>;
using vs = vector<str>;
using vpi = vector<pi>;
using vpl = vector<pl>;
using vpd = vector<pd>;

#define mp make_pair
#define f first
#define s second

#define sz(x) (int)(x).size()
#define bg(x) begin(x)
#define all(x) bg(x), end(x)
#define sor(x) sort(all(x))
#define ft front()
#define bk back()
#define pb push_back
#define pf push_front

#define lb lower_bound
#define ub upper_bound

#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define F0R(i, a) FOR(i, 0, a)
#define ROF(i, a, b) for (int i = (b) - 1; i >= (a); i--)
#define R0F(i, a) ROF(i, 0, a)
#define EACH(a, x) for (auto& a : x)

const int MOD = 1e9 + 7;
const int MXN = 2e5 + 10;
const int MXR = 25010;
const ll INF = 1e18;

const int BLOCK = 450;

int N, R, Q; vi adj[MXN]; int L[MXN]; // L[i] = Region of i

int timer = 1, in[MXN], out[MXN]; 

vi S1[MXR]; // Sorted list that divide into intervals
vi S2[MXR]; // Sorted list of all

int active[MXR];

vi large; int up[BLOCK][MXR], down[BLOCK][MXR];

int ind[MXR];

// Preorder Traversal ~ O(N)

void DFS(int X, int P) {
    in[X] = timer++; active[L[X]]++; S2[L[X]].pb(X);
    
    EACH(Y, adj[X]) if (Y != P) DFS(Y, X);

    out[X] = timer - 1; active[L[X]]--; 
    
    if (!active[L[X]]) S1[L[X]].pb(X);
}

// Get the answer when queried (A, B) ~ O(N)

int genAns(int A, int B) {
    int ans = 0; int L = 0, R = 0; int last = 0;

    while (L < sz(S1[A]) || R < sz(S2[B])) {
        if (L < sz(S1[A]) && (R >= sz(S2[B]) || in[S1[A][L]] < in[S2[B][R]])) last = out[S1[A][L++]];
        
        else { if (out[S2[B][R]] <= last) ans++; R++; }
    }
    return ans;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);

    cin >> N >> R >> Q >> L[1];

    FOR(i, 2, N + 1) { int A; cin >> A >> L[i]; adj[A].pb(i), adj[i].pb(A); }

    DFS(1, 0); 

    int cur = 0; FOR(i, 1, R + 1) if (sz(S2[i]) >= BLOCK) large.pb(i), ind[i] = cur++;

    F0R(i, sz(large)) {
        FOR(j, 1, R + 1) { 
            up[i][j] = genAns(large[i], j); 
            down[i][j] = genAns(j, large[i]); 
        }
    }
    F0R(i, Q) {
        int A, B; cin >> A >> B;
        
        if (sz(S2[A]) >= BLOCK) cout << up[ind[L[A]]][B] << "\n";
        
        else if (sz(S2[B]) >= BLOCK) cout << down[ind[L[A]]][B] << "\n";
        
        else cout << genAns(A, B) << "\n";
    }
}

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5 ms 6088 KB Time limit exceeded (wall clock)
2 Execution timed out 4 ms 6088 KB Time limit exceeded (wall clock)
3 Execution timed out 4 ms 6088 KB Time limit exceeded (wall clock)
4 Execution timed out 4 ms 6088 KB Time limit exceeded (wall clock)
5 Execution timed out 5 ms 6216 KB Time limit exceeded (wall clock)
6 Execution timed out 5 ms 6216 KB Time limit exceeded (wall clock)
7 Execution timed out 5 ms 6216 KB Time limit exceeded (wall clock)
8 Execution timed out 5 ms 6216 KB Time limit exceeded (wall clock)
9 Execution timed out 6 ms 6728 KB Time limit exceeded (wall clock)
10 Execution timed out 8 ms 6728 KB Time limit exceeded (wall clock)
11 Execution timed out 10 ms 6984 KB Time limit exceeded (wall clock)
12 Execution timed out 13 ms 7368 KB Time limit exceeded (wall clock)
13 Execution timed out 14 ms 7496 KB Time limit exceeded (wall clock)
14 Execution timed out 15 ms 7768 KB Time limit exceeded (wall clock)
15 Execution timed out 22 ms 10696 KB Time limit exceeded (wall clock)

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 45 ms 10944 KB Time limit exceeded (wall clock)
2 Execution timed out 56 ms 10432 KB Time limit exceeded (wall clock)
3 Execution timed out 56 ms 12740 KB Time limit exceeded (wall clock)
4 Execution timed out 17 ms 8008 KB Time limit exceeded (wall clock)
5 Execution timed out 19 ms 9672 KB Time limit exceeded (wall clock)
6 Execution timed out 506 ms 13264 KB Time limit exceeded (wall clock)
7 Execution timed out 206 ms 11756 KB Time limit exceeded (wall clock)
8 Execution timed out 1039 ms 24512 KB Time limit exceeded (wall clock)
9 Execution timed out 71 ms 15552 KB Time limit exceeded (wall clock)
10 Execution timed out 1458 ms 31984 KB Time limit exceeded (wall clock)
11 Execution timed out 95 ms 17764 KB Time limit exceeded (wall clock)
12 Execution timed out 1622 ms 16756 KB Time limit exceeded (wall clock)
13 Execution timed out 1503 ms 17536 KB Time limit exceeded (wall clock)
14 Execution timed out 3324 ms 21040 KB Time limit exceeded (wall clock)
15 Execution timed out 2533 ms 22012 KB Time limit exceeded (wall clock)
16 Execution timed out 1373 ms 29464 KB Time limit exceeded (wall clock)
17 Execution timed out 2499 ms 30912 KB Time limit exceeded (wall clock)