Submission #1119416

#	Time	Username	Problem	Language	Result	Execution time	Memory
1119416		ezzzay	Zoo (COCI19_zoo)	C++14	110 / 110	124 ms	40868 KiB

zoo

#include<bits/stdc++.h>
using namespace std;
#define int long long 
#define ff first
#define ss second
#define pb push_back
const int N=4444;
char a[N][N];
bool vis[N][N];
int xx[4]={1,-1,0,0};
int yy[4]={0,0,1,-1};
pair<int,int>par[N][N];
int lvl[N][N];
bool lvlvis[N*N];
signed main(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++)cin>>a[i][j];
    }
    queue<pair<int,int>>q,hq;
    q.push({n,m});
    int p=1;
    while(!(q.empty() and hq.empty())){
        int y,x;
        if(!q.empty()){
            y=q.front().ff,x=q.front().ss;
            q.pop();
            if(vis[y][x])continue;
        }
        else{
            y=hq.front().ff,x=hq.front().ss;
            hq.pop();
            if(vis[y][x]==0){
                int py=par[y][x].ff,px=par[y][x].ss;
                if(lvlvis[lvl[py][px]]==0)p++;
                lvlvis[lvl[py][px]]=1;
            }
        }
        if(y<1 or y>n or x<1 or x>m)continue;
        vis[y][x]=1;
        lvl[y][x]=p;
        for(int i=0;i<4;i++){
            if(vis[y+yy[i]][x+xx[i]]==0){
                if(a[y+yy[i]][x+xx[i]]==a[y][x]){
                    q.push({y+yy[i],x+xx[i]});
                }
                else if(a[y+yy[i]][x+xx[i]]=='T' or a[y+yy[i]][x+xx[i]]=='B'){
                    par[y+yy[i]][x+xx[i]]={y,x};
                    hq.push({y+yy[i],x+xx[i]});
                }
            }
        }
    }
    cout<<p;
}

• Subtask 1: 45 / 45
• Subtask 2: 65 / 65