Submission #716913

#	Time	Username	Problem	Language	Result	Execution time	Memory
716913		Jarif_Rahman	Tropical Garden (IOI11_garden)	C++17	69 / 100	5041 ms	50208 KiB

garden

#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 / 49
• Subtask 2: 20 / 20
• Subtask 3: 0 / 31