QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#367046#8236. Snake MovesurenjamtsTL 0ms7768kbC++172.2kb2024-03-25 16:35:332024-03-25 16:35:34

Judging History

你现在查看的是最新测评结果

  • [2024-03-25 16:35:34]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:7768kb
  • [2024-03-25 16:35:33]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define mk make_pair
#define S second
#define F first
string s[3045];
ll ans[3045][3045];
bool vis[3045][3045];
map < pair< ll, ll >, ll > mp;
ll n,m;
void bfs( ll X, ll Y ){
	priority_queue < pair< ll, pair< ll, ll > >, vector< pair< ll, pair< ll, ll > > >,  greater< pair< ll, pair< ll, ll > > > > q;
	while( q.size() )
		q.pop();
	q.push( { 0, {X,Y} } );
	while( q.size() ){
		ll cst = q.top().F;
		ll x = q.top().S.F;
		ll y = q.top().S.S;
		q.pop();
		if( vis[x][y] == 1 )
			continue;
		ans[x][y] = cst;
		vis[x][y] = 1;
//		cout << x << " " << y << " " << ans[x][y] << "\n";
		ll move;
		move = max( ans[x][y]+1, cst + mp[{x-1,y}] -cst );
		if( x > 1 && s[x-1][y] != '#' && ans[x-1][y] > move ){
		    q.push( { move, {x-1, y} } );
		}
		move = max( ans[x][y]+1, mp[{x+1,y}] );
		
//		if( x == 2 && y == 4 ){
//			cout << "************\n";
//			cout << x+1 << " " << y << "\n";
//			cout << move << " " << ans[x+1][y] << "\n";
//			cout << "************\n";
//		}
		if( x < m && s[x+1][y] != '#' && ans[x+1][y] > move ){
			q.push( { move, {x+1, y} } );
		}
		move = max( ans[x][y]+1, mp[{x,y-1}] );
		if( y > 1 && s[x][y-1] != '#' && ans[x][y-1] > move ){
		    q.push( { move, {x, y-1} } );
		}
		move = max( ans[x][y]+1, mp[{x,y+1}] );
		if( y < n && s[x][y+1] != '#' && ans[x][y+1] > move ){
		    q.push( { move, {x, y+1} } );
		}
	}
}
int main(){
	ios_base::sync_with_stdio(NULL);
	cin.tie(NULL);
	cout.tie(NULL);
	unsigned long long sum = 0;
	ll k, x, y;
	set < pair < ll, pair< ll, ll > > > mogoi;
	cin >> n >> m >> k;
	ll headx, heady;
	for(int i = k; i >= 1; i -- ){
		cin >> x >> y;
		if( i == k )
			headx = x, heady = y;
		mp[ {x,y} ] = i;
	}
	for(int i = 1; i <= n; i ++ ){
		cin >> s[i];
		s[i] = "0" + s[i]; 
	}
	for(int i = 1; i <= n; i ++ ){
		for(int j = 1; j <= m; j ++ ){
			ans[i][j] = 1e18;
		}
	}
	ans[headx][heady] = 0;
	bfs( headx, heady );
	
	for(int i = 1; i <= n; i ++ ){
		for(int j = 1; j <= m; j ++ ){
//			cout << ans[i][j] << " ";
			if( s[i][j] != '#' && ans[i][j] != 1e18 )
				sum += ans[i][j]*ans[i][j];
		}
//		cout << "\n";
	}
	cout << sum << "\n";
}

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 5788kb

input:

4 5 5
3 5
3 4
3 3
3 2
4 2
.....
.....
.....
.....

output:

293

result:

ok single line: '293'

Test #2:

score: 0
Accepted
time: 0ms
memory: 5692kb

input:

2 2 4
1 1
1 2
2 2
2 1
..
..

output:

14

result:

ok single line: '14'

Test #3:

score: 0
Accepted
time: 0ms
memory: 7768kb

input:

5 5 3
1 2
1 1
2 1
.....
.###.
.#.#.
.###.
.....

output:

407

result:

ok single line: '407'

Test #4:

score: -100
Time Limit Exceeded

input:

3000 2900 1
1882 526
........................................................................................................#................................................................................................................................................................#................

output:


result: