Submission #1286501

#	Time	Username	Problem	Language	Result	Execution time	Memory
1286501		eri16	Obstacles for a Llama (IOI25_obstacles)	C++20	10 / 100	80 ms	34748 KiB

obstacles

#include <bits/stdc++.h>
using namespace std;

int arr1[200005];

int arr2[2][200005];
int vis[2][200005]={0};

int dx[4]={0,0,-1,1};
int dy[4]={-1,1,0,0};

int kk=0;

void dfs(int i,int j, int col){
    if (vis[i][j]==0){
        vis[i][j]=1;
        arr2[i][j]=col;
    
        for (int z=0; z<4; z++){
            
            int px=i+dx[z],py=j+dy[z];
            
            if (px>=0 && py>=0){
                dfs(px,py,col);
            }
        }
    }
}

void initialize(std::vector<int> T, std::vector<int> H){
    
    if (T.size()==1){
        kk=1;
        for (int i=0; i<H.size(); i++){
            arr1[i]=(T[0]>H[i]) ? 1 : 0;
        }
        
        int k=0;
        
        for (int i=0; i<H.size(); i++){
            
            if (arr1[i]==1){arr1[i]=k;}
            else{
                arr1[i]=-1;
                if (i>0){
                    if (arr1[i-1]!=-1){
                        k++;
                    }
                }
            }
        }
    }
    
    else{
        kk=2;
        for (int i=0; i<H.size(); i++){
            arr2[0][i]=(T[0]>H[i]) ? 1 : 0;
        }
        
        for (int i=0; i<H.size(); i++){
            arr2[1][i]=(T[T.size()-1]>H[i]) ? 1 : 0;
        }        
        
        int k=1;
        
        vis[0][H.size()]=1;
        vis[1][H.size()]=1;
        
        for (int i=0; i<2; i++){
            for (int j=0; j<H.size(); j++){if (vis[i][j]==0){dfs(i,j,k);k++;}
        }}
    }
}


bool can_reach(int L, int R, int S, int D){
    
    if (kk==1){
        if (arr1[S]==arr1[D] && arr1[S]!=-1){return true;}
    }
    if (kk==2){
        if (arr1[S]==arr1[D] && arr1[S]!=0){return true;}        
    }
    
    return false;
}

• Subtask 0: 0 / 0
• Subtask 1: 10 / 10
• Subtask 2: 0 / 14
• Subtask 3: 0 / 13
• Subtask 4: 0 / 21
• Subtask 5: 0 / 25
• Subtask 6: 0 / 17