Submission #372962

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
372962	2021-03-02T13:42:28 Z	sam571128	Patkice II (COCI21_patkice2)	C++14	110 / 110	1660 ms	365292 KB

Main

#include <bits/stdc++.h>
 
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
 
using namespace std;
 
const int N = 2e3+5, M = N*N;
char grid[N][N], fromc[M];
vector<pair<pair<int,int>,char>> adj[M];
int from[M];
int n,m,dis[M], sx, sy, ex, ey;
 
void add_edge(int u, int v, int w, char c){
    if(u==-1||v==-1) return;
    adj[u].push_back({{v,w},c});
}
 
int encode(int i, int j){
    if(i<0||j<0||i >= n || j >= m) return -1;
    return i*N+j+1;
}
 
pair<int,int> decode(int num){
    return {num/N, num%N-1};
}
 
signed main(){
    fastio
    cin >> n >> m;
    for(int i = 0;i < n;i++){
        for(int j = 0;j < m;j++){
            cin >> grid[i][j];
            if(grid[i][j]=='o') sx = i, sy = j;
            if(grid[i][j]=='x') ex = i, ey = j;
        }
    }
    for(int i = 0;i < n;i++){
        for(int j = 0;j < m;j++){
            int a = (grid[i][j]!='>'),b = (grid[i][j]!='^'),c = (grid[i][j]!='<'),d = (grid[i][j]!='v');
            if(grid[i][j]=='o') a = b = c = d = 0;
            add_edge(encode(i,j),encode(i,j+1),a,'>');
            add_edge(encode(i,j),encode(i-1,j),b,'^');
            add_edge(encode(i,j),encode(i,j-1),c,'<');
            add_edge(encode(i,j),encode(i+1,j),d,'v');
        }
    }
    priority_queue<pair<int,int>,vector<pair<int,int>>,greater<>> pq;
    fill(dis,dis+M,1e9+7);
    dis[encode(sx,sy)] = 0;
    pq.push({0,encode(sx,sy)});
    while(!pq.empty()){
        auto [ww,u] = pq.top(); pq.pop();
        if(ww > dis[u]) continue;
        for(auto [p,c] : adj[u]){
            auto [v,w] = p;
            if(dis[v] > dis[u]+w){
                dis[v] = dis[u]+w;
                from[v] = u;
                fromc[v] = c;
                pq.push({dis[v],v});
            }
        }
    }
    cout << dis[encode(ex,ey)] << "\n";
    while(grid[ex][ey]!='o'){
        char c = fromc[encode(ex,ey)];
        auto p = decode(from[encode(ex,ey)]);
        ex = p.first, ey = p.second;
        if(ex==sx&&ey==sy) break;
        grid[ex][ey] = c;
    }
    for(int i = 0;i < n;i++){
        for(int j = 0;j < m;j++){
            cout << grid[i][j];
        }
        cout << "\n";
    }
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:52:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   52 |         auto [ww,u] = pq.top(); pq.pop();
      |              ^
Main.cpp:54:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   54 |         for(auto [p,c] : adj[u]){
      |                  ^
Main.cpp:55:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   55 |             auto [v,w] = p;
      |                  ^

Subtask #1

30.0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	67 ms	110572 KB	Output is correct
2	Correct	67 ms	110572 KB	Output is correct
3	Correct	75 ms	110572 KB	Output is correct
4	Correct	69 ms	110700 KB	Output is correct
5	Correct	67 ms	110444 KB	Output is correct

Subtask #2

80.0 / 80.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	67 ms	110572 KB	Output is correct
2	Correct	67 ms	110572 KB	Output is correct
3	Correct	75 ms	110572 KB	Output is correct
4	Correct	69 ms	110700 KB	Output is correct
5	Correct	67 ms	110444 KB	Output is correct
6	Correct	268 ms	148844 KB	Output is correct
7	Correct	291 ms	153716 KB	Output is correct
8	Correct	616 ms	204780 KB	Output is correct
9	Correct	1027 ms	264696 KB	Output is correct
10	Correct	1594 ms	329492 KB	Output is correct
11	Correct	1660 ms	365292 KB	Output is correct