Submission #716894

#	Time	Username	Problem	Language	Result	Execution time	Memory
716894		Jarif_Rahman	Tropical Garden (IOI11_garden)	C++17	0 / 100	1 ms	596 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;

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

vector<int> succ;
vector<int> cnt;
vector<int> mx, smx;
vector<int> state;
vector<int> cycle_nodes;

vector<vector<pair<int, int>>> cycle_p;
vector<vector<int>> path_p;

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

void dfs(int nd){
    if(state[nd] > 0){
        if(state[nd] == 1) cycle_nodes.pb(nd);
        return;
    }
    state[nd] = 1;
    dfs(succ[nd]);
    state[nd] = 2;
}
void dfs2(int nd){
    if(state[nd]) return;
    state[nd] = 1;
    dfs2(succ[nd]);

    if(node(nd) == P) path_p[nd].pb(0);
    for(int x: path_p[succ[nd]]) path_p[nd].pb(x+1);
    for(auto [a, b]: cycle_p[succ[nd]]) cycle_p[nd].pb({a+1, b});
}

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);
    cnt.assign(n+1, 0);
    mx.assign(n, 2*m-1), smx.assign(n, 2*m+1);

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

    state.assign(2*m, 0);
    for(int i = 0; i < n; i++) dfs(mx[i]);

    cycle_p.resize(2*m);
    path_p.resize(2*m);
    state.assign(2*m, 0);
    
    for(int nd: cycle_nodes){
        int ln = 1;
        if(node(nd) == P) cycle_p[nd].pb({0, -1});
        int x = succ[nd];
        while(x != nd){
            if(node(x) == P) cycle_p[nd].pb({ln, -1});
            ln++;
            x = succ[x];
        }
        for(auto &[a, b]: cycle_p[nd]) b = ln;
        state[nd] = 1;
    }

    for(int i = 0; i < n; i++) dfs2(mx[i]);
    vector<pair<int, int>> op;
    for(int i = 0; i < n; i++){
        for(int x: path_p[mx[i]]) cnt[x+1]++;
        for(auto [a, b]: cycle_p[mx[i]]) op.pb({a+1, b});
    }

    for(int i = 0; i < q; i++){
        int ans = 0;
        if(G[i] <= n) ans+=cnt[G[i]];
        for(auto [a, b]: op) if(a <= G[i] && (G[i]-a)%b == 0) ans++;
        answer(ans);
    }
}

• Subtask 1: 0 / 49
• Subtask 2: 0 / 20
• Subtask 3: 0 / 31