QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#594839 | #8236. Snake Move | absabs | WA | 576ms | 225392kb | C++23 | 4.2kb | 2024-09-28 10:36:49 | 2024-09-28 10:37:02 |
Judging History
answer
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define debug(x) cout << #x << "=" << x << endl
// using i128 = __int128_t;
#define int unsigned long long
typedef pair<int, int> PII;
typedef long long ll;
inline void read(int &x)
{
char ch = getchar();
int f = 1;
x = 0;
while (!isdigit(ch) && ch ^ '-')
ch = getchar();
if (ch == '-')
f = -1, ch = getchar();
while (isdigit(ch))
x = x * 10 + ch - '0', ch = getchar();
x *= f;
}
void write(int x)
{
if (x < 0)
putchar('-'), x = -x;
if (x > 9)
write(x / 10);
putchar(x % 10 + '0');
return;
}
// int a[N];
const int N = 5e5 + 10;
const int mod = 1e9 + 7;
#define pre(i, a, b) for (int i = a; i <= b; i++)
int qmi(int a, int b)
{
int res = 1;
while (b)
{
if (b & 1)
res = res * a % mod;
a = a * a % mod;
b >>= 1;
}
return res;
}
ll ans[N];
ll n, m, k;
ll tim[3010][3010];
char v[3010][3010];
ll dist[3010][3010];
ll dx[] = {1, -1, 0, 0};
ll dy[] = {0, 0, 1, -1};
ll vis[3010][3010];
ll st[3010][3010];
queue<PII> q;
void rCL()
{
cin >> n >> m >> k;
// cout<<n<<endl;
// return;
vector<PII> poi;
int aa, bb;
for (int i = 1; i <= k; i++)
{
int a, b;
cin >> a >> b;
poi.push_back({a, b});
if (i == 1)
{
aa = a;
bb = b;
continue;
}
// if (i == 1)
// continue;
// if (i != k)
tim[a][b] = k - i + 1;
}
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
cin >> v[i][j];
}
}
vis[aa][bb] = 1;
q.push({aa, bb});
while (!q.empty())
{
int x = q.front().first;
int y = q.front().second;
q.pop();
for (int i = 0; i < 4; i++)
{
int xx = x + dx[i];
int yy = y + dy[i];
if (xx < 1 || xx > n || yy<1 | yy> m || v[xx][yy] == '#' || vis[xx][yy])
continue;
if (dist[x][y] + 1 < tim[xx][yy])
continue;
q.push({xx, yy});
vis[xx][yy] = 1;
dist[xx][yy] = dist[x][y] + 1;
}
}
if (poi.size() > 2)
poi.pop_back();
for (int i = 0; i < poi.size(); i++)
{
if (i == 0)
continue;
int a = poi[i].first;
int b = poi[i].second;
st[a][b] = 1;
dist[a][b] = k + i - 2;
q.push({a, b});
}
/////
while (!q.empty())
{
int x = q.front().first;
int y = q.front().second;
q.pop();
// cout<<xx<<" "<<yy<<endl;
for (int i = 0; i < 4; i++)
{
int xx = x + dx[i];
int yy = y + dy[i];
if (xx < 1 || xx > n || yy<1 | yy> m || v[xx][yy] == '#' || st[xx][yy])
continue;
if (dist[x][y] + 1 < tim[xx][yy])
continue;
q.push({xx, yy});
st[xx][yy] = 1;
dist[xx][yy] = min(dist[xx][yy], dist[x][y] + 1);
}
}
///
reverse(poi.begin(), poi.end());
if (poi.size() > 2)
poi.pop_back();
for (auto [a, b] : poi)
{
for (int i = 0; i < 4; i++)
{
int xx = a + dx[i];
int yy = b + dy[i];
if (xx < 1 || xx > n || yy<1 | yy> m || v[xx][yy] == '#')
continue;
if (dist[xx][yy] + 1 < tim[a][b])
continue;
dist[a][b] = min(dist[xx][yy] + 1, dist[a][b]);
}
}
int ans = 0;
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
if (i == aa && j == bb)
{
continue;
}
int qwq = max(dist[i][j], (tim[i][j]));
qwq = dist[i][j];
ans += qwq * qwq;
}
}
cout << ans << endl;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int O_o = 1;
// cin >> O_o;
while (O_o--)
{
rCL();
}
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 11788kb
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: 12060kb
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: 11800kb
input:
5 5 3 1 2 1 1 2 1 ..... .###. .#.#. .###. .....
output:
407
result:
ok single line: '407'
Test #4:
score: 0
Accepted
time: 291ms
memory: 156168kb
input:
3000 2900 1 1882 526 ........................................................................................................#................................................................................................................................................................#................
output:
35141960580077
result:
ok single line: '35141960580077'
Test #5:
score: 0
Accepted
time: 364ms
memory: 153844kb
input:
2900 3000 1 1333 1773 .....#....#......#.#..#...#.....#.#.#.#....#...###.#..#.....##....####..#......#.......######.#........#..#......#...###.#.#..#.....#.#........##..#..#.#..#.###.#.#...#..#.##..#...#....#..#.##..#......#.######............#.#...#......#......#..#.#.#.#...#...#..##........#.###.....
output:
17464052497724
result:
ok single line: '17464052497724'
Test #6:
score: 0
Accepted
time: 55ms
memory: 18320kb
input:
3000 3000 1 2755 225 ##..#.##.....####..#...###.#.##.#.##.#......###.#####..#..####....#.#.####..##..##.#...#...##..#.#.##..#....##.#...#.....##.#...##.##.##..##..#######.####.####......##.##.#....#..#.....#..##.#.#...#.####..##.#..#...###..###.#.#...##.#.....###.####......##...#...#....#.#...#.#.#....
output:
255915
result:
ok single line: '255915'
Test #7:
score: 0
Accepted
time: 61ms
memory: 17972kb
input:
3000 2900 1 878 738 #.##.##..##.#.#.###.#...###.####.#.###.####.##.#.#####.#.####..#.#.###.###..####.####...###..####.########..##..#####.#....#####.#.#########..#.###.##.##.#####.#####.#.##..###..##.#####.#.############..##.###.##.##..########.#.###..###...######.####...#######.###.###..####.######...
output:
1
result:
ok single line: '1'
Test #8:
score: -100
Wrong Answer
time: 576ms
memory: 225392kb
input:
2900 3000 10 2883 1758 2883 1759 2883 1760 2883 1761 2883 1762 2884 1762 2884 1763 2883 1763 2882 1763 2882 1764 ........................................................#............................#........................................................................................................
output:
49803365625314
result:
wrong answer 1st lines differ - expected: '49803365625286', found: '49803365625314'