oj.uz

답안 #106896

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
106896 2019-04-20T20:37:19 Z wilwxk 포탈들 (BOI14_portals) C++11
70 / 100
 706 ms 263168 KB 
#include <bits/stdc++.h>
using namespace std;

const int MAXN=1e6+5;
const int MAXNN=1e3+3;
map<int, int> 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, int c, int k) {
	if(a==b) 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=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: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

# 결과 실행 시간 메모리 Grader output
1 Correct 46 ms 47484 KB Output is correct
2 Correct 46 ms 47480 KB Output is correct
3 Correct 56 ms 47480 KB Output is correct
4 Correct 54 ms 47352 KB Output is correct
5 Correct 45 ms 47480 KB Output is correct
6 Correct 49 ms 47484 KB Output is correct
7 Correct 44 ms 47480 KB Output is correct
8 Correct 45 ms 47488 KB Output is correct
9 Correct 48 ms 47484 KB Output is correct
10 Correct 51 ms 47352 KB Output is correct

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 44 ms 47352 KB Output is correct
2 Correct 45 ms 47476 KB Output is correct
3 Correct 44 ms 47428 KB Output is correct
4 Correct 43 ms 47352 KB Output is correct
5 Correct 47 ms 47352 KB Output is correct
6 Correct 44 ms 47356 KB Output is correct
7 Correct 46 ms 47480 KB Output is correct
8 Correct 46 ms 47488 KB Output is correct
9 Correct 59 ms 49016 KB Output is correct
10 Correct 51 ms 48888 KB Output is correct
11 Correct 45 ms 48120 KB Output is correct
12 Correct 44 ms 48404 KB Output is correct
13 Correct 46 ms 48248 KB Output is correct
14 Correct 45 ms 47352 KB Output is correct
15 Correct 47 ms 48420 KB Output is correct
16 Correct 45 ms 47368 KB Output is correct

Subtask #3
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 45 ms 47376 KB Output is correct
2 Correct 42 ms 47352 KB Output is correct
3 Correct 42 ms 47352 KB Output is correct
4 Correct 47 ms 47488 KB Output is correct
5 Correct 84 ms 54484 KB Output is correct
6 Correct 84 ms 54892 KB Output is correct
7 Correct 84 ms 55928 KB Output is correct
8 Correct 86 ms 54008 KB Output is correct

Subtask #4
19.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 43 ms 47340 KB Output is correct
2 Correct 44 ms 47464 KB Output is correct
3 Correct 42 ms 47356 KB Output is correct
4 Correct 43 ms 47360 KB Output is correct
5 Correct 44 ms 47472 KB Output is correct
6 Correct 45 ms 47480 KB Output is correct
7 Correct 45 ms 47480 KB Output is correct
8 Correct 46 ms 47480 KB Output is correct
9 Correct 47 ms 48896 KB Output is correct
10 Correct 49 ms 48888 KB Output is correct
11 Correct 46 ms 48120 KB Output is correct
12 Correct 44 ms 48120 KB Output is correct
13 Correct 45 ms 48268 KB Output is correct
14 Correct 80 ms 54392 KB Output is correct
15 Correct 83 ms 54860 KB Output is correct
16 Correct 79 ms 55928 KB Output is correct
17 Correct 86 ms 57080 KB Output is correct
18 Correct 98 ms 59516 KB Output is correct
19 Correct 91 ms 66156 KB Output is correct
20 Correct 116 ms 66136 KB Output is correct
21 Correct 86 ms 54552 KB Output is correct
22 Correct 79 ms 54520 KB Output is correct
23 Correct 90 ms 55160 KB Output is correct
24 Correct 140 ms 66040 KB Output is correct
25 Correct 42 ms 47352 KB Output is correct
26 Correct 48 ms 48512 KB Output is correct
27 Correct 44 ms 47480 KB Output is correct
28 Correct 91 ms 53932 KB Output is correct

Subtask #5
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 43 ms 47480 KB Output is correct
2 Correct 43 ms 47440 KB Output is correct
3 Correct 43 ms 47452 KB Output is correct
4 Correct 47 ms 47352 KB Output is correct
5 Correct 44 ms 47480 KB Output is correct
6 Correct 42 ms 47480 KB Output is correct
7 Correct 44 ms 47456 KB Output is correct
8 Correct 44 ms 47480 KB Output is correct
9 Correct 48 ms 48888 KB Output is correct
10 Correct 47 ms 48896 KB Output is correct
11 Correct 53 ms 48148 KB Output is correct
12 Correct 48 ms 48376 KB Output is correct
13 Correct 46 ms 48248 KB Output is correct
14 Correct 107 ms 54452 KB Output is correct
15 Correct 91 ms 54932 KB Output is correct
16 Correct 80 ms 55872 KB Output is correct
17 Correct 85 ms 56920 KB Output is correct
18 Correct 98 ms 59384 KB Output is correct
19 Correct 100 ms 66296 KB Output is correct
20 Correct 127 ms 66084 KB Output is correct
21 Correct 82 ms 54520 KB Output is correct
22 Correct 82 ms 54524 KB Output is correct
23 Correct 88 ms 55288 KB Output is correct
24 Runtime error 706 ms 263168 KB Execution killed with signal 9 (could be triggered by violating memory limits)
25 Halted 0 ms 0 KB -