제출 #1251989

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1251989		lambd47	열대 식물원 (Tropical Garden) (IOI11_garden)	C++20	49 / 100	5094 ms	19488 KiB

garden

#include <bits/stdc++.h>

#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#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 kek, int R[][2], int Q, int G[]){
    vector<int> vai(2*n,-1);
    vector<int> resps(Q);
    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);
    }
    auto solv=[&](int k){
        vector<int> vis(2*n);
        vector<int> st;
        st.push_back(k);
        int at=k;
        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);
        vector<bool> marc(2*n);
        L(i,0,sz(ciclo)-1){
            pos[ciclo[i]]=i;
            marc[ciclo[i]]=1;
            rep[ciclo[i]]=i;
            prof[ciclo[i]]=0;
        }
        auto dfsmarc=[&](auto&&self, int node, int pai)->void{
            marc[node]=1;
            rep[node]=pai;
            for(auto a:adjr[node]){
                if(marc[a])continue;
                self(self,a,pai);
            }
        };
        L(i,0,sz(ciclo)-1){
            dfsmarc(dfsmarc,ciclo[i],i);
        }
        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(!marc[i])continue;
            if(prof[i]==-1)busca(busca,i);
        }

        for(int receba=0;receba<Q;receba++){
            int dd=G[receba];
            int d=dd;
            int resp=0;
            if(prof[k]==0){
                L(i,0,n-1){
                    if(!marc[i])continue;
                    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++;
                    d=dd;
                }
            }
            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});
                    }
                }
            }
            resps[receba]+=resp;
        }
    };
    solv(kek);
    solv(kek+n);
    L(i,0,Q-1)answer(resps[i]);

}

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