QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#367055 | #8236. Snake Move | surenjamts | WA | 1677ms | 96492kb | C++17 | 2.0kb | 2024-03-25 16:50:50 | 2024-03-25 16:50:51 |
Judging History
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";
}
Details
Tip: Click on the bar to expand more detailed information
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'