oj.uz

답안 #372962

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
372962 2021-03-02T13:42:28 Z sam571128 Patkice II (COCI21_patkice2) C++14
110 / 110
 1660 ms 365292 KB 
#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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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