QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#367055#8236. Snake MovesurenjamtsWA 1677ms96492kbC++172.0kb2024-03-25 16:50:502024-03-25 16:50:51

Judging History

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

  • [2024-03-25 16:50:51]
  • 评测
  • 测评结果:WA
  • 用时:1677ms
  • 内存:96492kb
  • [2024-03-25 16:50:50]
  • 提交

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], mp[3045][3045];
bool vis[3045][3045];
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 < 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] = 1e9+7;
		}
	}
	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] != 1e9+7 ){
				unsigned long long num = ans[i][j];
				sum += num*num;
			}
		}
//		cout << "\n";
	}
	cout << sum << "\n";
}

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 7732kb

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: 1ms
memory: 7760kb

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: 1ms
memory: 7768kb

input:

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

output:

407

result:

ok single line: '407'

Test #4:

score: -100
Wrong Answer
time: 1677ms
memory: 96492kb

input:

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

output:

33741543195789

result:

wrong answer 1st lines differ - expected: '35141960580077', found: '33741543195789'