oj.uz

Submission #106900

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

const int MAXN=1e6+5;
const int MAXNN=1e3+5;
map<int, short> g[MAXN];
set< pair<int, int> > s;
short ori[MAXNN][MAXNN];
short parede[5][MAXNN][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; 
		s.insert({dist[i], i});
	}
	while(!s.empty()) {
		int cur=s.begin()->second;
		if(cur==chegada) return;
		s.erase(s.begin());
		for(auto aresta : g[cur]) {
			int viz=aresta.first; int peso=aresta.second;
			if(dist[viz]>dist[cur]+peso) {
				s.erase({dist[viz], viz});
				dist[viz]=dist[cur]+peso;
				s.insert({dist[viz], viz});
			}
		}
	}
}

int main() {
	scanf("%d %d", &nn, &mm);
	for(int i=1; i<=nn; i++) {
		char cc[MAXNN]; 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[1][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[2][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[4][i][j]=ult;
		}
		ult=1;
		for(int i=1; i<=nn; i++) {
			if(ori[i][j]!=0) { ult=i+1; continue; }
			parede[3][i][j]=ult;

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

			int cur=quem(i, j);
			liga(cur, quem(i, parede[1][i][j]), min(melhor, aa), 0);
			liga(cur, quem(i, parede[2][i][j]), min(melhor, bb), 0);
			liga(cur, quem(parede[3][i][j], j), min(melhor, cc), 0);
			liga(cur, quem(parede[4][i][j], j), min(melhor, dd), 0);
		}
	}
	// for(int i=1; i<=nn; i++) { for(int j=1; j<=mm; j++) printf("%d ", parede[3][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:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   char cc[MAXNN]; scanf(" %s", &cc[1]);
                   ~~~~~^~~~~~~~~~~~~~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 47352 KB Output is correct
2 Correct 46 ms 47480 KB Output is correct
3 Correct 44 ms 47352 KB Output is correct
4 Correct 44 ms 47412 KB Output is correct
5 Correct 41 ms 47352 KB Output is correct
6 Correct 43 ms 47480 KB Output is correct
7 Correct 43 ms 47488 KB Output is correct
8 Correct 43 ms 47488 KB Output is correct
9 Correct 43 ms 47424 KB Output is correct
10 Correct 44 ms 47352 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 47352 KB Output is correct
2 Correct 45 ms 47352 KB Output is correct
3 Correct 44 ms 47452 KB Output is correct
4 Correct 43 ms 47608 KB Output is correct
5 Correct 42 ms 47480 KB Output is correct
6 Correct 43 ms 47612 KB Output is correct
7 Correct 43 ms 47488 KB Output is correct
8 Correct 45 ms 47480 KB Output is correct
9 Correct 55 ms 49016 KB Output is correct
10 Correct 47 ms 48888 KB Output is correct
11 Correct 44 ms 48120 KB Output is correct
12 Correct 49 ms 48248 KB Output is correct
13 Correct 47 ms 48248 KB Output is correct
14 Correct 43 ms 47408 KB Output is correct
15 Correct 45 ms 48476 KB Output is correct
16 Correct 43 ms 47352 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 47352 KB Output is correct
2 Correct 41 ms 47408 KB Output is correct
3 Correct 42 ms 47612 KB Output is correct
4 Correct 43 ms 47408 KB Output is correct
5 Correct 87 ms 54392 KB Output is correct
6 Correct 121 ms 54904 KB Output is correct
7 Correct 88 ms 55964 KB Output is correct
8 Correct 84 ms 54008 KB Output is correct

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 47380 KB Output is correct
2 Correct 44 ms 47480 KB Output is correct
3 Correct 50 ms 47480 KB Output is correct
4 Correct 44 ms 47380 KB Output is correct
5 Correct 44 ms 47480 KB Output is correct
6 Correct 44 ms 47480 KB Output is correct
7 Correct 44 ms 47460 KB Output is correct
8 Correct 45 ms 47480 KB Output is correct
9 Correct 46 ms 48860 KB Output is correct
10 Correct 57 ms 48752 KB Output is correct
11 Correct 47 ms 48120 KB Output is correct
12 Correct 46 ms 48248 KB Output is correct
13 Correct 47 ms 48248 KB Output is correct
14 Correct 88 ms 54456 KB Output is correct
15 Correct 100 ms 54904 KB Output is correct
16 Correct 87 ms 55924 KB Output is correct
17 Correct 120 ms 56952 KB Output is correct
18 Correct 136 ms 59384 KB Output is correct
19 Correct 127 ms 66168 KB Output is correct
20 Correct 145 ms 66268 KB Output is correct
21 Correct 85 ms 54648 KB Output is correct
22 Correct 87 ms 54648 KB Output is correct
23 Correct 89 ms 55160 KB Output is correct
24 Correct 163 ms 66040 KB Output is correct
25 Correct 45 ms 47352 KB Output is correct
26 Correct 47 ms 48504 KB Output is correct
27 Correct 45 ms 47324 KB Output is correct
28 Correct 81 ms 54012 KB Output is correct

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 47356 KB Output is correct
2 Correct 43 ms 47380 KB Output is correct
3 Correct 43 ms 47480 KB Output is correct
4 Correct 44 ms 47352 KB Output is correct
5 Correct 44 ms 47360 KB Output is correct
6 Correct 46 ms 47352 KB Output is correct
7 Correct 44 ms 47352 KB Output is correct
8 Correct 43 ms 47480 KB Output is correct
9 Correct 49 ms 48760 KB Output is correct
10 Correct 48 ms 48760 KB Output is correct
11 Correct 45 ms 48120 KB Output is correct
12 Correct 49 ms 48120 KB Output is correct
13 Correct 48 ms 48248 KB Output is correct
14 Correct 86 ms 54392 KB Output is correct
15 Correct 90 ms 54904 KB Output is correct
16 Correct 103 ms 55964 KB Output is correct
17 Correct 106 ms 56896 KB Output is correct
18 Correct 113 ms 59476 KB Output is correct
19 Correct 149 ms 66168 KB Output is correct
20 Correct 144 ms 66296 KB Output is correct
21 Correct 83 ms 54520 KB Output is correct
22 Correct 86 ms 54640 KB Output is correct
23 Correct 91 ms 55160 KB Output is correct
24 Runtime error 905 ms 263168 KB Execution killed with signal 9 (could be triggered by violating memory limits)
25 Halted 0 ms 0 KB -