oj.uz

Submission #106893

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

const int MAXN=1e6+5;
const int MAXNN=1e3+3;
set<pair<int, int> > g[MAXN];
priority_queue< pair<int, int> > pq;
short ori[MAXNN][MAXNN];
int 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, int c, int k) {
	if(a==b) return;
	// g[a].push_back(b); if(k) g[b].push_back(a);
	// pes[a].push_back(c); if(k) pes[b].push_back(c);
	g[a].insert({b, c});
	if(k) g[b].insert({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++) {
		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=1;
		for(int i=1; i<=nn; i++) {
			if(ori[i][j]!=0) { ult=i+1; continue; }
			parede[3][i][j]=ult;
		}
		ult=nn;
		for(int i=nn; i>=1; i--) {
			if(ori[i][j]!=0) { ult=i-1; continue; }
			parede[4][i][j]=ult;
		}
	}

	for(int i=1; i<=nn; i++) {
		for(int j=1; j<=mm; j++) {
			if(ori[i][j]!=0) continue;
			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:44: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:46: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 45 ms 47352 KB Output is correct
2 Correct 45 ms 47480 KB Output is correct
3 Correct 45 ms 47480 KB Output is correct
4 Correct 43 ms 47352 KB Output is correct
5 Correct 45 ms 47480 KB Output is correct
6 Correct 45 ms 47544 KB Output is correct
7 Correct 45 ms 47480 KB Output is correct
8 Correct 45 ms 47480 KB Output is correct
9 Correct 44 ms 47352 KB Output is correct
10 Correct 44 ms 47360 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 47324 KB Output is correct
2 Correct 43 ms 47480 KB Output is correct
3 Correct 43 ms 47608 KB Output is correct
4 Correct 42 ms 47352 KB Output is correct
5 Correct 44 ms 47480 KB Output is correct
6 Correct 43 ms 47452 KB Output is correct
7 Correct 44 ms 47452 KB Output is correct
8 Correct 42 ms 47480 KB Output is correct
9 Correct 49 ms 49144 KB Output is correct
10 Correct 46 ms 49144 KB Output is correct
11 Correct 49 ms 48504 KB Output is correct
12 Correct 44 ms 48504 KB Output is correct
13 Correct 45 ms 48632 KB Output is correct
14 Correct 42 ms 47352 KB Output is correct
15 Correct 44 ms 48760 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 47360 KB Output is correct
2 Correct 42 ms 47676 KB Output is correct
3 Correct 43 ms 47480 KB Output is correct
4 Correct 46 ms 47484 KB Output is correct
5 Correct 63 ms 54772 KB Output is correct
6 Correct 75 ms 55284 KB Output is correct
7 Correct 65 ms 56184 KB Output is correct
8 Correct 66 ms 54264 KB Output is correct

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 47352 KB Output is correct
2 Correct 44 ms 47480 KB Output is correct
3 Correct 45 ms 47480 KB Output is correct
4 Correct 51 ms 47480 KB Output is correct
5 Correct 43 ms 47524 KB Output is correct
6 Correct 51 ms 47480 KB Output is correct
7 Correct 43 ms 47480 KB Output is correct
8 Correct 43 ms 47484 KB Output is correct
9 Correct 57 ms 49144 KB Output is correct
10 Correct 51 ms 49144 KB Output is correct
11 Correct 45 ms 48504 KB Output is correct
12 Correct 44 ms 48524 KB Output is correct
13 Correct 45 ms 48632 KB Output is correct
14 Correct 62 ms 55036 KB Output is correct
15 Correct 68 ms 55256 KB Output is correct
16 Correct 75 ms 56312 KB Output is correct
17 Correct 75 ms 57464 KB Output is correct
18 Correct 92 ms 59720 KB Output is correct
19 Correct 111 ms 66552 KB Output is correct
20 Correct 100 ms 66428 KB Output is correct
21 Correct 88 ms 54872 KB Output is correct
22 Correct 67 ms 54904 KB Output is correct
23 Correct 70 ms 55416 KB Output is correct
24 Correct 108 ms 66420 KB Output is correct
25 Correct 43 ms 47352 KB Output is correct
26 Correct 46 ms 48768 KB Output is correct
27 Correct 43 ms 47352 KB Output is correct
28 Correct 70 ms 54392 KB Output is correct

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 47252 KB Output is correct
2 Correct 48 ms 47480 KB Output is correct
3 Correct 46 ms 47544 KB Output is correct
4 Correct 46 ms 47364 KB Output is correct
5 Correct 47 ms 47480 KB Output is correct
6 Correct 44 ms 47488 KB Output is correct
7 Correct 51 ms 47432 KB Output is correct
8 Correct 45 ms 47480 KB Output is correct
9 Correct 47 ms 49144 KB Output is correct
10 Correct 45 ms 49144 KB Output is correct
11 Correct 45 ms 48504 KB Output is correct
12 Correct 52 ms 48508 KB Output is correct
13 Correct 54 ms 48632 KB Output is correct
14 Correct 67 ms 54900 KB Output is correct
15 Correct 68 ms 55284 KB Output is correct
16 Correct 72 ms 56184 KB Output is correct
17 Correct 74 ms 57336 KB Output is correct
18 Correct 81 ms 59764 KB Output is correct
19 Correct 83 ms 66680 KB Output is correct
20 Correct 106 ms 66552 KB Output is correct
21 Correct 81 ms 54860 KB Output is correct
22 Correct 68 ms 54940 KB Output is correct
23 Correct 66 ms 55416 KB Output is correct
24 Correct 938 ms 246484 KB Output is correct
25 Runtime error 412 ms 263168 KB Execution killed with signal 9 (could be triggered by violating memory limits)
26 Halted 0 ms 0 KB -