Submission #768820

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
768820	2023-06-28T16:59:09 Z	1075508020060209tc	Patkice II (COCI21_patkice2)	C++14	110 / 110	1495 ms	184676 KB

Main

#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];
pair<int,int>frm[2010][2010];
int fc[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;

priority_queue<pair<int,pair<int,int>>,vector<pair<int,pair<int,int> >>,greater<pair<int,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({0,{i,j}});
            dis[i][j]=0;
        }
    }
}
while(q.size()){
    int nwx=q.top().second.first;
    int nwy=q.top().second.second;
    q.pop();
    if(vis[nwx][nwy]){continue;}
    vis[nwx][nwy]=1;
    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]){continue;}
            dis[x][y]=0;
            q.push({0,{x,y}});
            frm[x][y]={nwx,nwy};
            fc[x][y]=i;
        }
        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[x][y]==dc[i]){
            dis[x][y]=w;
            q.push({dis[x][y],{x,y}});
            frm[x][y]={nwx,nwy};
            fc[x][y]=i;
        }else{
            dis[x][y]=w;
            q.push({dis[x][y],{x,y}});
            frm[x][y]={nwx,nwy};
            fc[x][y]=i;
        }
    }
}
/*
for(int i=1;i<=n;i++){
    for(int j=1;j<=m;j++){
        cout<<dis[i][j]<<" ";
    }cout<<endl;
}
*/
int nwx;int nwy;
for(int i=1;i<=n;i++){
    for(int j=1;j<=m;j++){
        if(gr[i][j]=='x'){
            cout<<dis[i][j]<<endl;
            nwx=i;nwy=j;
        }
    }
}
while(gr[nwx][nwy]!='o'){
    char c=dc[fc[nwx][nwy]];
    int x=frm[nwx][nwy].first;
    int y=frm[nwx][nwy].second;
    nwx=x;nwy=y;
    if(gr[x][y]=='o'){break;}
    gr[nwx][nwy]=c;
}



for(int i=1;i<=n;i++){
    for(int j=1;j<=m;j++){
        cout<<gr[i][j];
    }cout<<endl;
}



}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:94:18: warning: 'nwy' may be used uninitialized in this function [-Wmaybe-uninitialized]
   94 | while(gr[nwx][nwy]!='o'){
      |                  ^
Main.cpp:97:9: warning: 'nwx' may be used uninitialized in this function [-Wmaybe-uninitialized]
   97 |     int y=frm[nwx][nwy].second;
      |         ^

Subtask #1

30.0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	468 KB	Output is correct
2	Correct	0 ms	468 KB	Output is correct
3	Correct	1 ms	596 KB	Output is correct
4	Correct	1 ms	596 KB	Output is correct
5	Correct	0 ms	340 KB	Output is correct

Subtask #2

80.0 / 80.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	468 KB	Output is correct
2	Correct	0 ms	468 KB	Output is correct
3	Correct	1 ms	596 KB	Output is correct
4	Correct	1 ms	596 KB	Output is correct
5	Correct	0 ms	340 KB	Output is correct
6	Correct	156 ms	30620 KB	Output is correct
7	Correct	195 ms	41988 KB	Output is correct
8	Correct	418 ms	70584 KB	Output is correct
9	Correct	824 ms	119952 KB	Output is correct
10	Correct	1020 ms	144292 KB	Output is correct
11	Correct	1495 ms	184676 KB	Output is correct