oj.uz

답안 #106894

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
106894 2019-04-20T20:33:28 Z wilwxk 포탈들 (BOI14_portals) C++11
70 / 100
 564 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];
set< pair<int, int> > s;
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].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; 
		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:43: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:45: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 43 ms 47352 KB Output is correct
2 Correct 52 ms 47484 KB Output is correct
3 Correct 43 ms 47464 KB Output is correct
4 Correct 43 ms 47480 KB Output is correct
5 Correct 47 ms 47480 KB Output is correct
6 Correct 42 ms 47480 KB Output is correct
7 Correct 43 ms 47504 KB Output is correct
8 Correct 47 ms 47480 KB Output is correct
9 Correct 42 ms 47352 KB Output is correct
10 Correct 44 ms 47380 KB Output is correct

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 43 ms 47340 KB Output is correct
2 Correct 43 ms 47516 KB Output is correct
3 Correct 50 ms 47480 KB Output is correct
4 Correct 44 ms 47480 KB Output is correct
5 Correct 47 ms 47452 KB Output is correct
6 Correct 44 ms 47480 KB Output is correct
7 Correct 46 ms 47608 KB Output is correct
8 Correct 44 ms 47480 KB Output is correct
9 Correct 46 ms 49144 KB Output is correct
10 Correct 56 ms 49272 KB Output is correct
11 Correct 48 ms 48508 KB Output is correct
12 Correct 46 ms 48512 KB Output is correct
13 Correct 47 ms 48632 KB Output is correct
14 Correct 43 ms 47484 KB Output is correct
15 Correct 47 ms 48888 KB Output is correct
16 Correct 45 ms 47352 KB Output is correct

Subtask #3
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 44 ms 47408 KB Output is correct
2 Correct 43 ms 47480 KB Output is correct
3 Correct 124 ms 47484 KB Output is correct
4 Correct 42 ms 47480 KB Output is correct
5 Correct 79 ms 55928 KB Output is correct
6 Correct 91 ms 56440 KB Output is correct
7 Correct 82 ms 57464 KB Output is correct
8 Correct 70 ms 55544 KB Output is correct

Subtask #4
19.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 43 ms 47352 KB Output is correct
2 Correct 45 ms 47480 KB Output is correct
3 Correct 48 ms 47548 KB Output is correct
4 Correct 43 ms 47352 KB Output is correct
5 Correct 47 ms 47480 KB Output is correct
6 Correct 43 ms 47608 KB Output is correct
7 Correct 44 ms 47528 KB Output is correct
8 Correct 49 ms 47480 KB Output is correct
9 Correct 49 ms 49144 KB Output is correct
10 Correct 54 ms 49144 KB Output is correct
11 Correct 46 ms 48508 KB Output is correct
12 Correct 48 ms 48632 KB Output is correct
13 Correct 44 ms 48632 KB Output is correct
14 Correct 82 ms 56060 KB Output is correct
15 Correct 81 ms 56440 KB Output is correct
16 Correct 80 ms 57464 KB Output is correct
17 Correct 85 ms 58616 KB Output is correct
18 Correct 96 ms 61048 KB Output is correct
19 Correct 85 ms 67832 KB Output is correct
20 Correct 110 ms 67708 KB Output is correct
21 Correct 78 ms 56056 KB Output is correct
22 Correct 81 ms 56184 KB Output is correct
23 Correct 84 ms 56700 KB Output is correct
24 Correct 125 ms 67580 KB Output is correct
25 Correct 43 ms 47480 KB Output is correct
26 Correct 46 ms 49016 KB Output is correct
27 Correct 44 ms 47352 KB Output is correct
28 Correct 79 ms 55544 KB Output is correct

Subtask #5
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 45 ms 47352 KB Output is correct
2 Correct 50 ms 47480 KB Output is correct
3 Correct 47 ms 47520 KB Output is correct
4 Correct 44 ms 47480 KB Output is correct
5 Correct 43 ms 47536 KB Output is correct
6 Correct 43 ms 47480 KB Output is correct
7 Correct 45 ms 47480 KB Output is correct
8 Correct 41 ms 47480 KB Output is correct
9 Correct 47 ms 49188 KB Output is correct
10 Correct 45 ms 49144 KB Output is correct
11 Correct 47 ms 48468 KB Output is correct
12 Correct 48 ms 48504 KB Output is correct
13 Correct 49 ms 48632 KB Output is correct
14 Correct 81 ms 56056 KB Output is correct
15 Correct 86 ms 56440 KB Output is correct
16 Correct 81 ms 57464 KB Output is correct
17 Correct 88 ms 58684 KB Output is correct
18 Correct 97 ms 60920 KB Output is correct
19 Correct 95 ms 67704 KB Output is correct
20 Correct 110 ms 67704 KB Output is correct
21 Correct 78 ms 56056 KB Output is correct
22 Correct 78 ms 56184 KB Output is correct
23 Correct 90 ms 56824 KB Output is correct
24 Runtime error 564 ms 263168 KB Execution killed with signal 9 (could be triggered by violating memory limits)
25 Halted 0 ms 0 KB -