oj.uz

Submission #70797

# Submission time Handle Problem Language Result Execution time Memory
70797 2018-08-23T12:15:10 Z 검수컵(#1978, imsifile) Aquatic Labyrinth (FXCUP3_aqua) C++
100 / 100
 1476 ms 288612 KB 
#include<stdio.h>
#include<vector>
#include<queue>
using namespace std;

typedef long long lld;

struct dd {
	int ix; lld v;
	dd(int ix_, lld v_){ ix=ix_, v=v_; }
	bool operator< (const dd& c) const {
		return v>c.v;
	}
};

int N, nod[910][910], vcn, st, en;
char mz[910][910];
vector<int> con[3010101], val[3010101];
priority_queue<dd> pq;
lld dist[3010101];

int sq(int a){ return a*a; }

void edge(int s, int e, lld v){
	con[s].push_back(e), val[s].push_back(v);
}

int main(){
	scanf("%d", &N);
	for(int i=0; i<N; i++){
		scanf("\n%s", mz[i]);
		for(int j=0; j<N; j++){
			if(mz[i][j]=='W') continue;
			if(mz[i][j]=='M') st=vcn;
			if(mz[i][j]=='H') en=vcn;
			nod[i][j]=vcn++;
		}
	}
	for(int i=0; i<N; i++){
		for(int j=0; j<N; j++){
			if(!j || mz[i][j]!='W') continue;
			int j2;
			for(j2=j; j2<N && mz[i][j2]=='W'; j2++);
			if(j2==N) break;
			j2--;
			for(int k=j-1; k>=0 && mz[i][k]!='W'; k--){
				edge(nod[i][k], vcn, sq(j2-j+1));
				edge(vcn+1, nod[i][k], 0);
			}
			for(int k=j2+1; k<N && mz[i][k]!='W'; k++){
				edge(nod[i][k], vcn+1, sq(j2-j+1));
				edge(vcn, nod[i][k], 0);
			}
			vcn+=2;
			j=j2;
		}
		for(int j=0; j<N; j++){
			if(!j || mz[j][i]!='W') continue;
			int j2;
			for(j2=j; j2<N && mz[j2][i]=='W'; j2++);
			if(j2==N) break;
			j2--;
			for(int k=j-1; k>=0 && mz[k][i]!='W'; k--){
				edge(nod[k][i], vcn, sq(j2-j+1));
				edge(vcn+1, nod[k][i], 0);
			}
			for(int k=j2+1; k<N && mz[k][i]!='W'; k++){
				edge(nod[k][i], vcn+1, sq(j2-j+1));
				edge(vcn, nod[k][i], 0);
			}
			vcn+=2;
			j=j2;
		}
	}
	for(int i=0; i<vcn; i++) dist[i]=-1;
	dist[st]=0, pq.push(dd(st,0));
	while(!pq.empty()){
		dd x=pq.top(); pq.pop();
		if(x.v != dist[x.ix]) continue;
		int s=x.ix;
		for(int i=con[s].size(); i--;){
			int e=con[s][i]; lld v=val[s][i];
			if(dist[e]<0 || dist[e]>x.v+v) dist[e]=x.v+v, pq.push(dd(e,x.v+v));
		}
	}
	printf("%lld\n", dist[en]);
	return 0;
}

Compilation message

aqua.cpp: In function 'int main()':
aqua.cpp:29:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &N);
  ~~~~~^~~~~~~~~~
aqua.cpp:31:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("\n%s", mz[i]);
   ~~~~~^~~~~~~~~~~~~~~

Subtask #1
36.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 126 ms 141688 KB Output is correct
2 Correct 122 ms 141796 KB Output is correct
3 Correct 135 ms 141960 KB Output is correct
4 Correct 141 ms 142480 KB Output is correct
5 Correct 142 ms 142480 KB Output is correct
6 Correct 129 ms 142936 KB Output is correct
7 Correct 138 ms 143572 KB Output is correct
8 Correct 131 ms 143572 KB Output is correct
9 Correct 141 ms 144212 KB Output is correct
10 Correct 133 ms 144212 KB Output is correct

Subtask #2
64.0 / 64.0

# Verdict Execution time Memory Grader output
1 Correct 126 ms 141688 KB Output is correct
2 Correct 122 ms 141796 KB Output is correct
3 Correct 135 ms 141960 KB Output is correct
4 Correct 141 ms 142480 KB Output is correct
5 Correct 142 ms 142480 KB Output is correct
6 Correct 129 ms 142936 KB Output is correct
7 Correct 138 ms 143572 KB Output is correct
8 Correct 131 ms 143572 KB Output is correct
9 Correct 141 ms 144212 KB Output is correct
10 Correct 133 ms 144212 KB Output is correct
11 Correct 280 ms 155604 KB Output is correct
12 Correct 531 ms 205880 KB Output is correct
13 Correct 1066 ms 207000 KB Output is correct
14 Correct 716 ms 207000 KB Output is correct
15 Correct 134 ms 207000 KB Output is correct
16 Correct 1446 ms 233852 KB Output is correct
17 Correct 1476 ms 234084 KB Output is correct
18 Correct 1118 ms 288612 KB Output is correct
19 Correct 732 ms 288612 KB Output is correct
20 Correct 127 ms 288612 KB Output is correct