QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#582562 | #8236. Snake Move | argtarg | WA | 490ms | 155020kb | C++20 | 1.7kb | 2024-09-22 16:50:37 | 2024-09-22 16:50:37 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define pii pair<int, int>
void solve();
signed main()
{
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int T = 1;
//cin >> T;
while (T--)solve();
return 0;
}
const int mod = 998244353;
#define ull unsigned long long
void solve() {
int n, m, k;
cin >> n >> m >> k;
vector<int>t(k + 1);
vector<int>v(n * m);
auto get = [&](int x, int y)->int {
return x * m + y;
};
vector<ull>ans(n * m,1e10);
vector<int>add(k + 1,-1);
queue<pii>q;
vector<bool>vis(n * m);
//return;
for (int i = 1; i <= k; i++) {
int x, y;
cin >> x >> y;
x--;
y--;
int j = get(x, y);
v[j] = k - i + 1;
if (i == 1) {
q.push({ 0,j });
vis[j] = 1;
}
}
vector<string>s(n);
for (int i = 0; i < n; i++) {
cin >> s[i];
for (int j = 0; j < m; j++) {
if (s[i][j] == '#') {
vis[get(i, j)] = 1;
}
}
}
vector<int>dx = { -1,1,0,0 };
vector<int>dy = { 0,0,-1,1 };
//return;
while (q.size()) {
pii it = q.front();
q.pop();
int u = it.second, id = it.first;
if (id<=k&&add[id] != -1) {
q.push({ id + 1,add[id] });
add[id] = -1;
}
ans[u] = min(ans[u], (ull)id);
int x = u / m, y = u % m;
for (int t = 0; t < 4; t++) {
int nx = dx[t] + x, ny = dy[t] + y;
int j = get(nx, ny);
if ( nx < 0 || nx >= n || ny < 0 || ny >= m||vis[j] == 1 )continue;
if (v[j] > id + 1) {
add[v[j] - 1] = j;
}
else {
vis[j] = 1;
q.push({ id + 1,j });
}
}
}
ull co = 0;
for (int i = 0; i < n * m; i++) {
if (ans[i] != 1e10) {
co += ans[i] * ans[i];
}
}
cout << co << endl;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3840kb
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: 3612kb
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: 3548kb
input:
5 5 3 1 2 1 1 2 1 ..... .###. .#.#. .###. .....
output:
407
result:
ok single line: '407'
Test #4:
score: 0
Accepted
time: 301ms
memory: 149680kb
input:
3000 2900 1 1882 526 ........................................................................................................#................................................................................................................................................................#................
output:
35141960580077
result:
ok single line: '35141960580077'
Test #5:
score: 0
Accepted
time: 339ms
memory: 149696kb
input:
2900 3000 1 1333 1773 .....#....#......#.#..#...#.....#.#.#.#....#...###.#..#.....##....####..#......#.......######.#........#..#......#...###.#.#..#.....#.#........##..#..#.#..#.###.#.#...#..#.##..#...#....#..#.##..#......#.######............#.#...#......#......#..#.#.#.#...#...#..##........#.###.....
output:
17464052497724
result:
ok single line: '17464052497724'
Test #6:
score: 0
Accepted
time: 59ms
memory: 154752kb
input:
3000 3000 1 2755 225 ##..#.##.....####..#...###.#.##.#.##.#......###.#####..#..####....#.#.####..##..##.#...#...##..#.#.##..#....##.#...#.....##.#...##.##.##..##..#######.####.####......##.##.#....#..#.....#..##.#.#...#.####..##.#..#...###..###.#.#...##.#.....###.####......##...#...#....#.#...#.#.#....
output:
255915
result:
ok single line: '255915'
Test #7:
score: 0
Accepted
time: 49ms
memory: 149656kb
input:
3000 2900 1 878 738 #.##.##..##.#.#.###.#...###.####.#.###.####.##.#.#####.#.####..#.#.###.###..####.####...###..####.########..##..#####.#....#####.#.#########..#.###.##.##.#####.#####.#.##..###..##.#####.#.############..##.###.##.##..########.#.###..###...######.####...#######.###.###..####.######...
output:
1
result:
ok single line: '1'
Test #8:
score: 0
Accepted
time: 292ms
memory: 149692kb
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:
49803365625286
result:
ok single line: '49803365625286'
Test #9:
score: 0
Accepted
time: 490ms
memory: 155020kb
input:
3000 3000 10 2015 1932 2015 1931 2015 1930 2015 1929 2016 1929 2017 1929 2018 1929 2018 1928 2018 1927 2017 1927 #...#...#..#.........#.......#####....#...###..#..###..###....##.....#..#..#...#.....##...##.#..#..##.###.........##.....#....#..##.##.#.#.##.#.#.#.....#....##.##.#..##....#....#...#.#......
output:
22509095749285
result:
ok single line: '22509095749285'
Test #10:
score: 0
Accepted
time: 47ms
memory: 149612kb
input:
3000 2900 10 326 1781 325 1781 325 1782 325 1783 325 1784 324 1784 324 1783 323 1783 323 1782 324 1782 ##.#....#.###.######..#.#.....##.#.##..####.####.##..#..#.###.#####....##.#.##.#..###..##.###.##.#####.###..##.#..##..##.#..##.#.#.##...##..#.##.##........#..#..###.##.###.####.#..########.##.....#...
output:
40571
result:
ok single line: '40571'
Test #11:
score: -100
Wrong Answer
time: 47ms
memory: 149744kb
input:
2900 3000 10 2447 135 2447 136 2447 137 2447 138 2447 139 2447 140 2448 140 2448 139 2449 139 2449 138 .#.##.##..#.###########.#####.###....#####.########..##..#.####.##.##.####.####..#.#####.##.#.#.###.##.#.##.####..##.#.####..###..###...##...##.#####.#####.#...#####.####..##.##.#.#..#..####.##..##...
output:
170
result:
wrong answer 1st lines differ - expected: '2705', found: '170'