Submission #372917

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
372917	2021-03-02T09:40:38 Z	sam571128	Patkice II (COCI21_patkice2)	C++14	30 / 110	1625 ms	524292 KB

Main

#include <bits/stdc++.h>

#define int long long
#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,1e18);
	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:53:8: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   53 |   auto [ww,u] = pq.top(); pq.pop();
      |        ^
Main.cpp:55:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   55 |   for(auto [p,c] : adj[u]){
      |            ^
Main.cpp:56:9: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   56 |    auto [v,w] = p;
      |         ^

Subtask #1

30.0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	79 ms	126316 KB	Output is correct
2	Correct	81 ms	126316 KB	Output is correct
3	Correct	79 ms	126444 KB	Output is correct
4	Correct	91 ms	126464 KB	Output is correct
5	Correct	91 ms	126188 KB	Output is correct

Subtask #2

0.0 / 80.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	79 ms	126316 KB	Output is correct
2	Correct	81 ms	126316 KB	Output is correct
3	Correct	79 ms	126444 KB	Output is correct
4	Correct	91 ms	126464 KB	Output is correct
5	Correct	91 ms	126188 KB	Output is correct
6	Correct	305 ms	190464 KB	Output is correct
7	Correct	340 ms	196828 KB	Output is correct
8	Correct	689 ms	287772 KB	Output is correct
9	Correct	1173 ms	395216 KB	Output is correct
10	Correct	1625 ms	508524 KB	Output is correct
11	Runtime error	671 ms	524292 KB	Execution killed with signal 9