oj.uz

답안 #106888

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

const int MAXN=1e6+5;
const int MAXNN=1e3+3;
vector<int> g[MAXN], pes[MAXN];
set<pair<int, int> > s;
int 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;
	//printf("%d liga %d c/ %d\n", a, b, c);
	g[a].push_back(b); if(k) g[b].push_back(a);
	pes[a].push_back(c); if(k) pes[b].push_back(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;
		// printf("cur %d // %d\n", cur, dist[cur]);
		s.erase(s.begin());
		for(int i=0; i<g[cur].size(); i++) {
			int viz=g[cur][i]; int peso=pes[cur][i];
			// printf("  // %d > %d\n", viz, peso);
			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 'void dijkstra(int)':
portals.cpp:33:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0; i<g[cur].size(); i++) {
                ~^~~~~~~~~~~~~~
portals.cpp: In function 'int main()':
portals.cpp:46: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:48: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 47 ms 47352 KB Output is correct
2 Correct 42 ms 47488 KB Output is correct
3 Correct 43 ms 47480 KB Output is correct
4 Correct 42 ms 47340 KB Output is correct
5 Correct 45 ms 47504 KB Output is correct
6 Correct 42 ms 47484 KB Output is correct
7 Correct 43 ms 47580 KB Output is correct
8 Correct 41 ms 47480 KB Output is correct
9 Correct 43 ms 47352 KB Output is correct
10 Correct 53 ms 47352 KB Output is correct

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 46 ms 47412 KB Output is correct
2 Correct 46 ms 47480 KB Output is correct
3 Correct 50 ms 47480 KB Output is correct
4 Correct 45 ms 47352 KB Output is correct
5 Correct 44 ms 47480 KB Output is correct
6 Correct 42 ms 47488 KB Output is correct
7 Correct 45 ms 47480 KB Output is correct
8 Correct 43 ms 47480 KB Output is correct
9 Correct 49 ms 48888 KB Output is correct
10 Correct 52 ms 48888 KB Output is correct
11 Correct 46 ms 48504 KB Output is correct
12 Correct 48 ms 48656 KB Output is correct
13 Correct 49 ms 48632 KB Output is correct
14 Correct 48 ms 47480 KB Output is correct
15 Correct 48 ms 48636 KB Output is correct
16 Correct 43 ms 47480 KB Output is correct

Subtask #3
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 48 ms 47352 KB Output is correct
2 Correct 52 ms 47484 KB Output is correct
3 Correct 43 ms 47480 KB Output is correct
4 Correct 45 ms 47612 KB Output is correct
5 Correct 91 ms 55800 KB Output is correct
6 Correct 100 ms 56056 KB Output is correct
7 Correct 81 ms 56568 KB Output is correct
8 Correct 82 ms 56056 KB Output is correct

Subtask #4
19.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 44 ms 47352 KB Output is correct
2 Correct 43 ms 47440 KB Output is correct
3 Correct 44 ms 47480 KB Output is correct
4 Correct 45 ms 47480 KB Output is correct
5 Correct 53 ms 47480 KB Output is correct
6 Correct 43 ms 47608 KB Output is correct
7 Correct 43 ms 47480 KB Output is correct
8 Correct 51 ms 47608 KB Output is correct
9 Correct 51 ms 48936 KB Output is correct
10 Correct 57 ms 48772 KB Output is correct
11 Correct 54 ms 48504 KB Output is correct
12 Correct 49 ms 48632 KB Output is correct
13 Correct 52 ms 48760 KB Output is correct
14 Correct 84 ms 55772 KB Output is correct
15 Correct 83 ms 56056 KB Output is correct
16 Correct 87 ms 56696 KB Output is correct
17 Correct 90 ms 56824 KB Output is correct
18 Correct 92 ms 57852 KB Output is correct
19 Correct 85 ms 59612 KB Output is correct
20 Correct 100 ms 59512 KB Output is correct
21 Correct 82 ms 55800 KB Output is correct
22 Correct 83 ms 55804 KB Output is correct
23 Correct 92 ms 56084 KB Output is correct
24 Correct 112 ms 59584 KB Output is correct
25 Correct 45 ms 47480 KB Output is correct
26 Correct 49 ms 48760 KB Output is correct
27 Correct 43 ms 47360 KB Output is correct
28 Correct 109 ms 56028 KB Output is correct

Subtask #5
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 43 ms 47480 KB Output is correct
2 Correct 42 ms 47480 KB Output is correct
3 Correct 43 ms 47568 KB Output is correct
4 Correct 44 ms 47480 KB Output is correct
5 Correct 43 ms 47480 KB Output is correct
6 Correct 43 ms 47628 KB Output is correct
7 Correct 43 ms 47480 KB Output is correct
8 Correct 44 ms 47480 KB Output is correct
9 Correct 47 ms 48888 KB Output is correct
10 Correct 47 ms 48888 KB Output is correct
11 Correct 47 ms 48604 KB Output is correct
12 Correct 48 ms 48760 KB Output is correct
13 Correct 46 ms 48632 KB Output is correct
14 Correct 81 ms 55800 KB Output is correct
15 Correct 82 ms 56076 KB Output is correct
16 Correct 81 ms 56760 KB Output is correct
17 Correct 83 ms 56828 KB Output is correct
18 Correct 98 ms 57848 KB Output is correct
19 Correct 82 ms 59716 KB Output is correct
20 Correct 96 ms 59544 KB Output is correct
21 Correct 90 ms 55800 KB Output is correct
22 Correct 81 ms 55888 KB Output is correct
23 Correct 84 ms 56184 KB Output is correct
24 Execution timed out 1075 ms 218720 KB Time limit exceeded
25 Halted 0 ms 0 KB -