oj.uz

Submission #716899

# Submission time Handle Problem Language Result Execution time Memory
716899 2023-03-31T10:47:06 Z Jarif_Rahman Tropical Garden (IOI11_garden) C++17
0 / 100
 1 ms 596 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, 2*m-1), smx.assign(n, 2*m-1);
    fill(anc, anc+K, vector<int>(2*m, 0));

    for(int i = 0; i < m; i++){
        if(i <= mx[R[i][0]]%m) smx[R[i][0]] = mx[R[i][0]], mx[R[i][0]] = i+m;
        else if(i <= smx[R[i][0]]) smx[R[i][0]] = i+m;
        if(i <= mx[R[i][1]]%m) smx[R[i][1]] = mx[R[i][1]], mx[R[i][1]] = i;
        else if(i <= smx[R[i][1]]) smx[R[i][1]] = 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 ? 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++){
        if(G[i] == 0){
            answer(1);
            continue;
        }
        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
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 0 ms 212 KB Output is correct
5 Incorrect 1 ms 340 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
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 0 ms 212 KB Output is correct
5 Incorrect 1 ms 340 KB Output isn't correct
6 Halted 0 ms 0 KB -

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 0 ms 212 KB Output is correct
5 Incorrect 1 ms 340 KB Output isn't correct
6 Halted 0 ms 0 KB -