oj.uz

Submission #106903

# Submission time Handle Problem Language Result Execution time Memory
106903 2019-04-20T20:51:59 Z wilwxk Portals (BOI14_portals) C++11
70 / 100
 1000 ms 237696 KB 
#include <bits/stdc++.h>
using namespace std;

const int MAXN=1e6+5;
const int MAXNN=1e3+5;
map<int, short> g[MAXN];
priority_queue< pair<int, int> > pq;
char ori[MAXNN][MAXNN];
short parede[4][MAXNN][MAXNN];
char cc[MAXNN];
int dist[MAXN];
int n, nn, mm, star, chegada;

int quem(int i, int j) {
	return (i-1)*mm+j;
}
void liga(int a, int b, short c, int k) {
	if(a==b||a<=0||b<=0) return;
	if(g[a][b]==0) g[a][b]=c;
	g[a][b]=min(g[a][b], c);
	if(k) {
		if(g[b][a]==0) g[b][a]=c;
		g[b][a]=min(g[b][a], c);
	}
}

void dijkstra(int star) {
	for(int i=1; i<=n; i++) {
		dist[i]=1e9+9; if(i==star) dist[i]=0; 
		pq.push({-dist[i], i});
	}
	while(!pq.empty()) {
		int cur=pq.top().second;
		if(cur==chegada) return;
		pq.pop();
		for(auto aresta : g[cur]) {
			int viz=aresta.first; int peso=aresta.second;
			if(dist[viz]>dist[cur]+peso) {
				dist[viz]=dist[cur]+peso;
				pq.push({-dist[viz], viz});
			}
		}
	}
}

int main() {
	scanf("%d %d", &nn, &mm);
	for(int i=1; i<=nn; i++) {
		scanf(" %s", &cc[1]);
		for(int j=1; j<=mm; j++) {
			char c=cc[j];
			if(c=='#') ori[i][j]=1;
			else ori[i][j]=0;
			if(c=='S') star=quem(i, j);
			if(c=='C') chegada=quem(i, j);
		}
	}

	for(int i=1; i<=nn; i++) {
		int ult=1;
		for(int j=1; j<=mm; j++) {
			if(ori[i][j]!=0) { ult=j+1; continue; }
			parede[0][i][j]=ult;

			if(i-1>=1&&ori[i-1][j]==0) liga(quem(i-1, j), quem(i, j), 1, 1);
			if(i+1<=nn&&ori[i+1][j]==0) liga(quem(i+1, j), quem(i, j), 1, 1);
			if(j-1>=1&&ori[i][j-1]==0) liga(quem(i, j-1), quem(i, j), 1, 1);
			if(j+1<=mm&&ori[i][j+1]==0) liga(quem(i, j+1), quem(i, j), 1, 1);
		}
		ult=mm;
		for(int j=mm; j>=1; j--) {
			if(ori[i][j]!=0) { ult=j-1; continue; }
			parede[1][i][j]=ult;
		}
	}

	for(int j=1; j<=mm; j++) {
		int ult=nn;
		for(int i=nn; i>=1; i--) {
			if(ori[i][j]!=0) { ult=i-1; continue; }
			parede[3][i][j]=ult;
		}
		ult=1;
		for(int i=1; i<=nn; i++) {
			if(ori[i][j]!=0) { ult=i+1; continue; }
			parede[2][i][j]=ult;

			int aa=abs(parede[0][i][j]-j);
			int bb=abs(parede[1][i][j]-j);
			int cc=abs(parede[2][i][j]-i);
			int dd=abs(parede[3][i][j]-i);
			int melhor=min(min(aa, bb), min(cc, dd))+1;

			int cur=quem(i, j);
			liga(cur, quem(i, parede[0][i][j]), min(melhor, aa), 0);
			liga(cur, quem(i, parede[1][i][j]), min(melhor, bb), 0);
			liga(cur, quem(parede[2][i][j], j), min(melhor, cc), 0);
			liga(cur, quem(parede[3][i][j], j), min(melhor, dd), 0);
		}
	}
	// for(int i=1; i<=nn; i++) { for(int j=1; j<=mm; j++) printf("%d ", parede[2][i][j]); printf("\n"); }

	n=nn*mm;
	dijkstra(star);
	// for(int i=1; i<=n; i++) printf("%d > %d\n", i, dist[i]);

	printf("%d\n", dist[chegada]);

}

Compilation message

portals.cpp: In function 'int main()':
portals.cpp:47:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &nn, &mm);
  ~~~~~^~~~~~~~~~~~~~~~~~~
portals.cpp:49:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf(" %s", &cc[1]);
   ~~~~~^~~~~~~~~~~~~~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 47352 KB Output is correct
2 Correct 43 ms 47480 KB Output is correct
3 Correct 43 ms 47396 KB Output is correct
4 Correct 42 ms 47352 KB Output is correct
5 Correct 54 ms 47480 KB Output is correct
6 Correct 45 ms 47352 KB Output is correct
7 Correct 43 ms 47480 KB Output is correct
8 Correct 46 ms 47608 KB Output is correct
9 Correct 43 ms 47352 KB Output is correct
10 Correct 43 ms 47352 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 47416 KB Output is correct
2 Correct 43 ms 47480 KB Output is correct
3 Correct 43 ms 47480 KB Output is correct
4 Correct 43 ms 47352 KB Output is correct
5 Correct 44 ms 47480 KB Output is correct
6 Correct 44 ms 47480 KB Output is correct
7 Correct 45 ms 47352 KB Output is correct
8 Correct 43 ms 47352 KB Output is correct
9 Correct 47 ms 48760 KB Output is correct
10 Correct 49 ms 48748 KB Output is correct
11 Correct 48 ms 47992 KB Output is correct
12 Correct 45 ms 48120 KB Output is correct
13 Correct 46 ms 48120 KB Output is correct
14 Correct 44 ms 47480 KB Output is correct
15 Correct 48 ms 48352 KB Output is correct
16 Correct 51 ms 47352 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 47300 KB Output is correct
2 Correct 44 ms 47420 KB Output is correct
3 Correct 44 ms 47372 KB Output is correct
4 Correct 43 ms 47480 KB Output is correct
5 Correct 74 ms 52992 KB Output is correct
6 Correct 89 ms 53416 KB Output is correct
7 Correct 75 ms 54524 KB Output is correct
8 Correct 70 ms 52444 KB Output is correct

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 47360 KB Output is correct
2 Correct 41 ms 47488 KB Output is correct
3 Correct 45 ms 47452 KB Output is correct
4 Correct 45 ms 47352 KB Output is correct
5 Correct 45 ms 47352 KB Output is correct
6 Correct 43 ms 47468 KB Output is correct
7 Correct 52 ms 47352 KB Output is correct
8 Correct 43 ms 47352 KB Output is correct
9 Correct 51 ms 48760 KB Output is correct
10 Correct 50 ms 48760 KB Output is correct
11 Correct 49 ms 47992 KB Output is correct
12 Correct 46 ms 48128 KB Output is correct
13 Correct 46 ms 48296 KB Output is correct
14 Correct 70 ms 52980 KB Output is correct
15 Correct 72 ms 53492 KB Output is correct
16 Correct 77 ms 54520 KB Output is correct
17 Correct 89 ms 55544 KB Output is correct
18 Correct 100 ms 58020 KB Output is correct
19 Correct 113 ms 64840 KB Output is correct
20 Correct 128 ms 64632 KB Output is correct
21 Correct 72 ms 52980 KB Output is correct
22 Correct 74 ms 53112 KB Output is correct
23 Correct 73 ms 53880 KB Output is correct
24 Correct 151 ms 64628 KB Output is correct
25 Correct 44 ms 47352 KB Output is correct
26 Correct 47 ms 48316 KB Output is correct
27 Correct 43 ms 47352 KB Output is correct
28 Correct 73 ms 52392 KB Output is correct

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 47352 KB Output is correct
2 Correct 43 ms 47480 KB Output is correct
3 Correct 44 ms 47480 KB Output is correct
4 Correct 41 ms 47352 KB Output is correct
5 Correct 42 ms 47480 KB Output is correct
6 Correct 46 ms 47408 KB Output is correct
7 Correct 42 ms 47480 KB Output is correct
8 Correct 42 ms 47480 KB Output is correct
9 Correct 48 ms 48732 KB Output is correct
10 Correct 46 ms 48760 KB Output is correct
11 Correct 44 ms 47992 KB Output is correct
12 Correct 45 ms 48248 KB Output is correct
13 Correct 45 ms 48124 KB Output is correct
14 Correct 67 ms 52980 KB Output is correct
15 Correct 74 ms 53492 KB Output is correct
16 Correct 93 ms 54392 KB Output is correct
17 Correct 80 ms 55544 KB Output is correct
18 Correct 97 ms 57972 KB Output is correct
19 Correct 108 ms 64760 KB Output is correct
20 Correct 121 ms 64760 KB Output is correct
21 Correct 68 ms 53108 KB Output is correct
22 Correct 66 ms 53112 KB Output is correct
23 Correct 74 ms 53752 KB Output is correct
24 Execution timed out 1097 ms 237696 KB Time limit exceeded
25 Halted 0 ms 0 KB -