oj.uz

Submission #716913

# Submission time Handle Problem Language Result Execution time Memory
716913 2023-03-31T11:45:42 Z Jarif_Rahman Tropical Garden (IOI11_garden) C++17
69 / 100
 5000 ms 50208 KB 
#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
#define pb push_back
#define f first
#define sc second
using namespace std;
typedef long long int ll;
typedef string str;

const int K = 30;

int n, m, q, P;
vector<vector<int>> R;

vector<int> succ;
vector<int> mx, smx;
vector<int> anc[K];

int node(int e){ return e < m ? R[e][0]:R[e-m][1]; };

int get_anc(int nd, int d){
    for(int i = 0; i < K; i++){
        if(d&1) nd = anc[i][nd];
        d>>=1;
    }
    return nd;
}

void count_routes(int _n, int _m, int _P, int _R[][2], int _q, int G[]){
    swap(n, _n), swap(m, _m), swap(P, _P), swap(q, _q);
    for(int i = 0; i < m; i++) R.pb({_R[i][0], _R[i][1]});

    succ.resize(2*m);
    mx.assign(n, -1), smx.assign(n, -1);
    fill(anc, anc+K, vector<int>(2*m, 0));

    for(int i = 0; i < m; i++){
        if(i < mx[R[i][0]]%m || mx[R[i][0]] == -1) smx[R[i][0]] = mx[R[i][0]], mx[R[i][0]] = i+m;
        else if(i < smx[R[i][0]]%m || smx[R[i][0]] == -1) smx[R[i][0]] = i+m;
        if(i < mx[R[i][1]]%m || mx[R[i][1]] == -1) smx[R[i][1]] = mx[R[i][1]], mx[R[i][1]] = i;
        else if(i < smx[R[i][1]]%m || smx[R[i][1]] == -1) smx[R[i][1]] = i;
    }

    for(int i = 0; i < n; i++) if(smx[i] == -1) smx[i] = mx[i];
    for(int i = 0; i < m; i++) succ[i] = (mx[R[i][0]]%m != i ? mx[R[i][0]]:smx[R[i][0]]);
    for(int i = m; i < 2*m; i++) succ[i] = (mx[R[i-m][1]]%m != i-m ? mx[R[i-m][1]]:smx[R[i-m][1]]);
    for(int i = 0; i < 2*m; i++) anc[0][i] = succ[i];

    for(int p = 1; p < K; p++) for(int i = 0; i < 2*m; i++)
        anc[p][i] = anc[p-1][anc[p-1][i]];

    for(int i = 0; i < q; i++){
        int ans = 0;
        for(int j = 0; j < n; j++) if(node(get_anc(mx[j], G[i]-1)) == P) ans++;
        answer(ans);
    }
}

Subtask #1
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 1 ms 304 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 2 ms 852 KB Output is correct
7 Correct 1 ms 300 KB Output is correct
8 Correct 2 ms 596 KB Output is correct
9 Correct 4 ms 2900 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 1 ms 304 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 2 ms 852 KB Output is correct
7 Correct 1 ms 300 KB Output is correct
8 Correct 2 ms 596 KB Output is correct
9 Correct 4 ms 2900 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 13 ms 7720 KB Output is correct
12 Correct 25 ms 17520 KB Output is correct
13 Correct 37 ms 28628 KB Output is correct
14 Correct 75 ms 47572 KB Output is correct
15 Correct 64 ms 49580 KB Output is correct
16 Correct 67 ms 45308 KB Output is correct
17 Correct 61 ms 45208 KB Output is correct
18 Correct 25 ms 17624 KB Output is correct
19 Correct 97 ms 47648 KB Output is correct
20 Correct 87 ms 49528 KB Output is correct
21 Correct 69 ms 45316 KB Output is correct
22 Correct 77 ms 45136 KB Output is correct
23 Correct 75 ms 50208 KB Output is correct

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 1 ms 304 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 2 ms 852 KB Output is correct
7 Correct 1 ms 300 KB Output is correct
8 Correct 2 ms 596 KB Output is correct
9 Correct 4 ms 2900 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 13 ms 7720 KB Output is correct
12 Correct 25 ms 17520 KB Output is correct
13 Correct 37 ms 28628 KB Output is correct
14 Correct 75 ms 47572 KB Output is correct
15 Correct 64 ms 49580 KB Output is correct
16 Correct 67 ms 45308 KB Output is correct
17 Correct 61 ms 45208 KB Output is correct
18 Correct 25 ms 17624 KB Output is correct
19 Correct 97 ms 47648 KB Output is correct
20 Correct 87 ms 49528 KB Output is correct
21 Correct 69 ms 45316 KB Output is correct
22 Correct 77 ms 45136 KB Output is correct
23 Correct 75 ms 50208 KB Output is correct
24 Correct 8 ms 376 KB Output is correct
25 Correct 2304 ms 7804 KB Output is correct
26 Correct 4032 ms 17652 KB Output is correct
27 Execution timed out 5041 ms 28664 KB Time limit exceeded
28 Halted 0 ms 0 KB -