Submission #1251282

#	Time	Username	Problem	Language	Result	Execution time	Memory
1251282		lambd47	Tropical Garden (IOI11_garden)	C++20	0 / 100	177 ms	327680 KiB

garden

#include <bits/stdc++.h>
#include "garden.h"
#include "gardenlib.h"

using namespace std;
#define L(i,j,k) for(int i=(j);i<=(k);i++)
#define R(i,j,k) for(int i=(j);i>=(k);i--)
#define sz(v) ((int)v.size())
#define all(v) (v).begin(),(v).end()
#define ll long long

void count_routes(int n, int m, int k, int R[][2], int Q, int G[]){
    vector<int> vai(2*n,-1);
    vector<vector<int>> adjr(2*n);
    L(i,0,m-1){
        auto [a,b]=R[i];
        bool oka=(vai[a]==-1);
        bool okb=(vai[b]==-1);
        if(vai[a]==-1){
            if(okb)vai[a]=b+n;
            else vai[a]=b;
        }
        else if(vai[a+n]==-1){
            if(okb)vai[a+n]=b+n;
            else vai[a+n]=b;
        }
        if(vai[b]==-1){
            if(oka)vai[b]=a+n;
            else vai[b]=a;

        }
        else if(vai[b+n]==-1){
            if(oka)vai[b+n]=a+n;
            else vai[b+n]=a;
        }
    }
    L(i,0,n-1){
        if(vai[i+n]==-1)vai[i+n]=vai[i];
    }
    L(i,0,2*n-1){
        adjr[vai[i]].push_back(i);
    }
    vector<int> vis(2*n);
    vector<int> st;
    st.push_back(0);
    int at=0;
    vis[at]=1;

    while(!vis[vai[at]]){
        vis[vai[at]]=1;
        st.push_back(vai[at]);
        at=vai[at];
    }
    vector<int> ciclo(1,at);
    vector<int> pos(2*n,-1);
    while(st.back()!=at){
        ciclo.push_back(st.back());
        st.pop_back();
    }
    reverse(all(ciclo));
    vector<int> prof(2*n,-1);
    vector<int> rep(2*n);
    L(i,0,sz(ciclo)-1){
        pos[ciclo[i]]=i;
        rep[ciclo[i]]=i;
        prof[ciclo[i]]=0;
    }
    auto busca=[&](auto&& self, int at)->int{
        if(prof[at]!=-1)return prof[at];
        return prof[at]=self(self,vai[at])+1;
    };
    L(i,0,2*n-1){
        if(prof[i]==-1)busca(busca,i);
    }

    for(int receba=0;receba<Q;receba++){
        int d=G[receba];
        int resp=0;
        if(prof[k]==0){
            L(i,0,n-1){
                if(d<prof[i])continue;
                d-=prof[i];
                int at=rep[i];
                d-=(pos[k]-at+sz(ciclo))%sz(ciclo);
                if(d>=0 && (d%sz(ciclo))==0)resp++;
            }
        }
        else{
            vector<pair<int,int>> fila;
            fila.push_back({0,k});
            while(!fila.empty()){
                auto [prf,v]=fila.back();
                fila.pop_back();
                if(prf==d){
                    if(v<n)resp++;

                }
                else{
                    for(auto a:adjr[v])fila.push_back({prf+1,a});
                }
            }
        }
        if(prof[k+n]==0){
            L(i,0,n-1){
                if(d<prof[i])continue;
                d-=prof[i];
                int at=rep[i];
                d-=(pos[k+n]-at+sz(ciclo))%sz(ciclo);
                if(d>=0 && (d%sz(ciclo))==0)resp++;
            }
        }
        else{
            vector<pair<int,int>> fila;
            fila.push_back({0,k+n});
            while(!fila.empty()){
                auto [prf,v]=fila.back();
                fila.pop_back();
                if(prf==d){
                    if(v<n)resp++;
                }
                else{
                    for(auto a:adjr[v])fila.push_back({prf+1,a});
                }
            }
        }
        answer(resp);
    }






}

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