QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#629748#8236. Snake MovetaijinvjinWA 666ms188564kbC++173.3kb2024-10-11 14:36:532024-10-11 14:36:53

Judging History

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

  • [2024-10-11 14:36:53]
  • 评测
  • 测评结果:WA
  • 用时:666ms
  • 内存:188564kb
  • [2024-10-11 14:36:53]
  • 提交

answer

#include <bits/stdc++.h>

#define u64 unsigned long long
#define PII std::pair<int, int>

int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};

struct node {
    int dis, id, cnt, len;
    bool operator < (const node &a) const {
        return dis > a.dis;
    }
};

void solve() {
    int n, m, k;
    std::cin >> n >> m >> k;
    std::vector<PII> snake(k + 1);

    for (int i = 1; i <= k; i ++) {
        std::cin >> snake[i].first >> snake[i].second;
    }

    std::vector<std::string> mp(n + 1);
    for (int i = 1; i <= n; i ++) {
        std::string s;
        std::cin >> s;
        s = ' ' + s;
        mp[i] = s;
    }

    auto getid = [&](int x, int y) -> int {
    	x --;
    	y --;
        return x * m + y + 1;
    };

    auto getpos = [&](int id) -> PII {
        return {(id - 1) / m + 1, (id - 1) % m + 1};
    };

    std::vector<std::vector<int>> Cnt(n + 1, std::vector<int>(m + 1, 0));
    auto dijkstra = [&](PII s) -> void {
        std::vector<u64> dis(n * m + 1, 1E9);
        std::vector<int> vis(n * m + 1, 0);
        std::vector<std::vector<int>> Mp(n + 1, std::vector<int>(m + 1, 1E9));
        for (int i = 1; i <= k; i ++) {
            Mp[snake[i].first][snake[i].second] = i;
        }
        // for (int i = 1; i <= n; i ++) {
        	// for (int j = 1; j <= m; j ++) std::cout << Mp[i][j] << " \n"[j == m];
        // }
        std::priority_queue<node> q;
        q.push({0, getid(s.first, s.second), 0, k});
        dis[getid(s.first, s.second)] = 0;
        while (!q.empty()) {
            auto [d, u, cnt, len] = q.top();
            q.pop();
            auto [x, y] = getpos(u);
            if (vis[u] == 1) continue;
            vis[u] = 1; 
            for (int i = 0; i < 4; i ++) {
                int nx = x + dx[i], ny = y + dy[i];
                int v = getid(nx, ny);
                if (nx < 1 || nx > n || ny < 1 || ny > m || mp[nx][ny] == '#') continue;
                if (len - Mp[nx][ny] - cnt > 0) {
                    int Len = Mp[nx][ny];
                    if (Len < 1) continue;
                    // std::cout << nx << " " << ny << " " << Len << "\n";
                    if (dis[v] > d + len - Len + 1) {
                        dis[v] = d + len - Len + 1;
                        q.push({dis[v], v, cnt + 1, Len});
                    }
                    continue;
                }
                v = getid(nx, ny);
                if (dis[v] > d + 1) {
                    dis[v] = d + 1;
                    q.push({dis[v], v, cnt + 1, len});
                }
                
            }
        }
        
        u64 Ans = 0;
        for (int i = 1; i <= n * m; i ++) {
        	auto P = getpos(i);
            Cnt[P.first][P.second] = dis[i];
            if (dis[i] == 1E9) continue;
            Ans += (dis[i]) * (dis[i]);
        }
        // for (int i = 1; i <= n; i ++) {
            // for (int j = 1; j <= m; j ++) {
                // std::cout << Cnt[i][j] << " \n"[j == m];
            // }
        // }
        std::cout << Ans << "\n";
    };

    dijkstra({snake[1].first, snake[1].second});
    
}

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int T = 1;
    // std::cin >> T;
    while (T --) {
        solve();
    }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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: 3620kb

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: 661ms
memory: 182324kb

input:

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

output:

35141960580077

result:

ok single line: '35141960580077'

Test #5:

score: 0
Accepted
time: 622ms
memory: 182324kb

input:

2900 3000 1
1333 1773
.....#....#......#.#..#...#.....#.#.#.#....#...###.#..#.....##....####..#......#.......######.#........#..#......#...###.#.#..#.....#.#........##..#..#.#..#.###.#.#...#..#.##..#...#....#..#.##..#......#.######............#.#...#......#......#..#.#.#.#...#...#..##........#.###.....

output:

17464052497724

result:

ok single line: '17464052497724'

Test #6:

score: 0
Accepted
time: 31ms
memory: 188264kb

input:

3000 3000 1
2755 225
##..#.##.....####..#...###.#.##.#.##.#......###.#####..#..####....#.#.####..##..##.#...#...##..#.#.##..#....##.#...#.....##.#...##.##.##..##..#######.####.####......##.##.#....#..#.....#..##.#.#...#.####..##.#..#...###..###.#.#...##.#.....###.####......##...#...#....#.#...#.#.#....

output:

255915

result:

ok single line: '255915'

Test #7:

score: 0
Accepted
time: 47ms
memory: 182072kb

input:

3000 2900 1
878 738
#.##.##..##.#.#.###.#...###.####.#.###.####.##.#.#####.#.####..#.#.###.###..####.####...###..####.########..##..#####.#....#####.#.#########..#.###.##.##.#####.#####.#.##..###..##.#####.#.############..##.###.##.##..########.#.###..###...######.####...#######.###.###..####.######...

output:

1

result:

ok single line: '1'

Test #8:

score: 0
Accepted
time: 666ms
memory: 182340kb

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: 627ms
memory: 188564kb

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: -100
Wrong Answer
time: 24ms
memory: 182060kb

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:

41221

result:

wrong answer 1st lines differ - expected: '40571', found: '41221'