oj.uz

Submission #768952

# Submission time Handle Problem Language Result Execution time Memory
768952 2023-06-29T01:02:07 Z 1075508020060209tc Patkice II (COCI21_patkice2) C++14
55 / 110
 317 ms 80920 KB 
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define X first
#define Y second
int n;int m;
int ok(int i,int j){
if(i>=1&&i<=n&&j>=1&&j<=m){return 1;}
return 0;
}
int dir[5]={0,1,0,-1,0};
char dc[5]={'!','>','v','<','^'};
string gr[2010];
int dis[2010][2010];
int vis[2010][2010];
signed main(){
//cin.tie(0);
//ios_base::sync_with_stdio(0);

cin>>n>>m;
for(int i=1;i<=n;i++){
    cin>>gr[i];
    gr[i]="*"+gr[i];
}
deque<pair<int,int>>q;
for(int i=1;i<=n;i++){
    for(int j=1;j<=m;j++){
        dis[i][j]=1e9;
        if(gr[i][j]=='o'){
            q.push_back({i,j});
            dis[i][j]=0;
        }
    }
}
while(q.size()){
    int nwx=q.front().first;
    int nwy=q.front().second;
    q.pop_front();
    if(vis[nwx][nwy]){continue;}
    vis[nwx][nwy]=1;
    //cout<<nwx<<" "<<nwy<<" "<<dis[nwx][nwy]<<endl;
    if(gr[nwx][nwy]=='o'){
        for(int i=1;i<=4;i++){
            int x=nwx+dir[i-1];
            int y=nwy+dir[i];
            if(!ok(x,y)||dis[x][y]<=dis[nwx][nwy]||vis[x][y]){continue;}
            dis[x][y]=0;
            q.push_front({x,y});
        }
        continue;
    }
    for(int i=1;i<=4;i++){
        int x=nwx+dir[i-1];
        int y=nwy+dir[i];
        int w=dis[nwx][nwy];
        if(gr[nwx][nwy]!=dc[i]){
            w++;
        }
        if(!ok(x,y)||dis[x][y]<=w||vis[x][y]){continue;}
        if(gr[nwx][nwy]==dc[i]){
            dis[x][y]=w;
            q.push_front({x,y});
        }else{
            dis[x][y]=w;
            q.push_back({x,y});
        }
    }
}
/*
for(int i=1;i<=n;i++){
    for(int j=1;j<=m;j++){
        cout<<dis[i][j]<<" ";
    }cout<<endl;
}
*/
for(int i=1;i<=n;i++){
    for(int j=1;j<=m;j++){
        if(gr[i][j]=='x'){
            cout<<dis[i][j]<<endl;
        }
    }
}
for(int i=1;i<=n;i++){
    for(int j=1;j<=m;j++){
        cout<<gr[i][j];
    }cout<<endl;
}



}

Subtask #1
15.0 / 30.0

# Verdict Execution time Memory Grader output
1 Partially correct 0 ms 340 KB Partially correct
2 Partially correct 0 ms 340 KB Partially correct
3 Partially correct 1 ms 468 KB Partially correct
4 Partially correct 0 ms 468 KB Partially correct
5 Partially correct 1 ms 340 KB Partially correct

Subtask #2
40.0 / 80.0

# Verdict Execution time Memory Grader output
1 Partially correct 0 ms 340 KB Partially correct
2 Partially correct 0 ms 340 KB Partially correct
3 Partially correct 1 ms 468 KB Partially correct
4 Partially correct 0 ms 468 KB Partially correct
5 Partially correct 1 ms 340 KB Partially correct
6 Partially correct 42 ms 13996 KB Partially correct
7 Partially correct 58 ms 18664 KB Partially correct
8 Partially correct 107 ms 31616 KB Partially correct
9 Partially correct 209 ms 54436 KB Partially correct
10 Partially correct 251 ms 61560 KB Partially correct
11 Partially correct 317 ms 80920 KB Partially correct