Submission #474948

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
474948	2021-09-20T10:12:08 Z	NTG	Patkice II (COCI21_patkice2)	C++11	110 / 110	1328 ms	78708 KB

Main

#include<bits/stdc++.h>
using namespace std;
const int N=2e3+1, oo=0x3f3f3f3f;
typedef pair<int,int> ii;
typedef tuple<int,int,int> iii;
#define fi first
#define sc second
#define ux(x) get<1>(x)
#define uy(x) get<2>(x)
#define w(x) get<0>(x)
int r,s,a[N][N];
char cc[7]={'o','x','.','>','<','v','^'};
int h[4]={0,0,1,-1}, c[4]={1,-1,0,0};
ii ss,ff;
bool check(int x, int n)
{
    return (x>0 && x<=n);
}
int d[N][N];
ii trace[N][N];
void dij()
{
    for(int i=0; i<=r+1; i++)
        for(int j=1; j<=s+1; j++) d[i][j]=oo, trace[i][j]={-1,-1};
    priority_queue<iii,vector<iii>,greater<iii>> q;
    q.push({0,ss.fi,ss.sc});
    d[ss.fi][ss.sc]=0;
    while(!q.empty())
    {
        int u1=ux(q.top());
        int u2=uy(q.top());
        int du=w(q.top());
        if(u1 == ff.fi && u2 == ff.sc) break;
        q.pop();
        if(du!=d[u1][u2]) continue;
        for(int i=0; i<4; i++)
            if(check(u1+h[i],r) && check(u2+c[i],s))
            {
                int v1=u1+h[i];
                int v2=u2+c[i];
                int t=1;
                if(i+3 == a[u1][u2] || (u1 == ss.fi && u2 == ss.sc)) t=0;
                if(d[v1][v2] > d[u1][u2] + t)
                {
                    d[v1][v2]=d[u1][u2]+t;
                    trace[v1][v2]={h[i],c[i]};
                    q.push({d[v1][v2],v1,v2});
                }
            }
    }
    cout<<d[ff.fi][ff.sc]<<'\n';
    ii t=ff;
    while(t!=ss)
    {
        ii tt=trace[t.fi][t.sc];
        t={t.fi-tt.fi,t.sc-tt.sc};
        for(int i=0; i<4; i++)
            if(tt.fi == h[i] && tt.sc == c[i]) {a[t.fi][t.sc]=i+3;break;}
    }
    a[ss.fi][ss.sc]=0;
    for(int i=1; i<=r; i++)
    {
        for(int j=1; j<=s; j++) cout<<cc[a[i][j]];
        cout<<'\n';
    }
}
int main()
{
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin>>r>>s;
    for(int i=1; i<=r; i++)
        for(int j=1; j<=s; j++)
        {
            char ch; cin>>ch;
            if(ch == 'o') a[i][j]=0, ss={i,j};
            if(ch == 'x') a[i][j]=1, ff={i,j};
            if(ch == '.') a[i][j]=2;
            if(ch == '>') a[i][j]=3;
            if(ch == '<') a[i][j]=4;
            if(ch == 'v') a[i][j]=5;
            if(ch == '^') a[i][j]=6;
        }
    dij();
    return 0;
}

Subtask #1

30.0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	332 KB	Output is correct
2	Correct	1 ms	460 KB	Output is correct
3	Correct	1 ms	460 KB	Output is correct
4	Correct	1 ms	460 KB	Output is correct
5	Correct	1 ms	332 KB	Output is correct

Subtask #2

80.0 / 80.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	332 KB	Output is correct
2	Correct	1 ms	460 KB	Output is correct
3	Correct	1 ms	460 KB	Output is correct
4	Correct	1 ms	460 KB	Output is correct
5	Correct	1 ms	332 KB	Output is correct
6	Correct	91 ms	16440 KB	Output is correct
7	Correct	114 ms	21808 KB	Output is correct
8	Correct	295 ms	34500 KB	Output is correct
9	Correct	573 ms	54008 KB	Output is correct
10	Correct	858 ms	61348 KB	Output is correct
11	Correct	1328 ms	78708 KB	Output is correct