/ SeriousOJ /

Record Detail

Accepted


  
# Status Time Cost Memory Cost
#1 Accepted 1ms 532.0 KiB
#2 Accepted 1ms 532.0 KiB
#3 Accepted 1ms 532.0 KiB
#4 Accepted 1ms 532.0 KiB
#5 Accepted 1ms 532.0 KiB
#6 Accepted 1ms 532.0 KiB
#7 Accepted 1ms 532.0 KiB
#8 Accepted 1ms 484.0 KiB
#9 Accepted 1ms 324.0 KiB
#10 Accepted 1ms 348.0 KiB
#11 Accepted 1ms 536.0 KiB
#12 Accepted 1ms 488.0 KiB
#13 Accepted 1ms 532.0 KiB
#14 Accepted 1ms 544.0 KiB
#15 Accepted 1ms 544.0 KiB
#16 Accepted 1ms 532.0 KiB
#17 Accepted 1ms 552.0 KiB
#18 Accepted 1ms 436.0 KiB
#19 Accepted 1ms 532.0 KiB
#20 Accepted 1ms 532.0 KiB
#21 Accepted 1ms 496.0 KiB
#22 Accepted 1ms 532.0 KiB
#23 Accepted 1ms 480.0 KiB
#24 Accepted 1ms 320.0 KiB
#25 Accepted 1ms 440.0 KiB
#26 Accepted 1ms 532.0 KiB
#27 Accepted 5ms 532.0 KiB
#28 Accepted 5ms 532.0 KiB
#29 Accepted 5ms 532.0 KiB
#30 Accepted 5ms 532.0 KiB
#31 Accepted 5ms 532.0 KiB
#32 Accepted 5ms 532.0 KiB
#33 Accepted 5ms 320.0 KiB
#34 Accepted 5ms 536.0 KiB
#35 Accepted 5ms 704.0 KiB
#36 Accepted 5ms 484.0 KiB
#37 Accepted 5ms 532.0 KiB
#38 Accepted 5ms 532.0 KiB
#39 Accepted 5ms 532.0 KiB
#40 Accepted 5ms 532.0 KiB
#41 Accepted 5ms 532.0 KiB
#42 Accepted 5ms 532.0 KiB
#43 Accepted 5ms 568.0 KiB
#44 Accepted 5ms 532.0 KiB
#45 Accepted 5ms 532.0 KiB
#46 Accepted 5ms 532.0 KiB
#47 Accepted 5ms 440.0 KiB
#48 Accepted 5ms 532.0 KiB
#49 Accepted 5ms 532.0 KiB
#50 Accepted 5ms 480.0 KiB
#51 Accepted 5ms 532.0 KiB
#52 Accepted 5ms 532.0 KiB
#53 Accepted 5ms 532.0 KiB
#54 Accepted 5ms 532.0 KiB
#55 Accepted 5ms 532.0 KiB
#56 Accepted 5ms 532.0 KiB
#57 Accepted 5ms 324.0 KiB
#58 Accepted 5ms 532.0 KiB
#59 Accepted 5ms 536.0 KiB
#60 Accepted 7ms 440.0 KiB
#61 Accepted 5ms 532.0 KiB
#62 Accepted 5ms 532.0 KiB
#63 Accepted 5ms 532.0 KiB
#64 Accepted 5ms 444.0 KiB
#65 Accepted 5ms 520.0 KiB
#66 Accepted 5ms 532.0 KiB
#67 Accepted 5ms 444.0 KiB
#68 Accepted 5ms 532.0 KiB
#69 Accepted 5ms 532.0 KiB
#70 Accepted 5ms 436.0 KiB
#71 Accepted 5ms 536.0 KiB
#72 Accepted 5ms 532.0 KiB
#73 Accepted 5ms 764.0 KiB
#74 Accepted 5ms 532.0 KiB
#75 Accepted 5ms 536.0 KiB
#76 Accepted 5ms 532.0 KiB
#77 Accepted 5ms 532.0 KiB
#78 Accepted 5ms 320.0 KiB
#79 Accepted 5ms 532.0 KiB
#80 Accepted 5ms 532.0 KiB
#81 Accepted 6ms 532.0 KiB
#82 Accepted 5ms 324.0 KiB
#83 Accepted 5ms 532.0 KiB
#84 Accepted 5ms 532.0 KiB
#85 Accepted 6ms 532.0 KiB
#86 Accepted 5ms 532.0 KiB
#87 Accepted 5ms 532.0 KiB
#88 Accepted 5ms 532.0 KiB
#89 Accepted 5ms 532.0 KiB
#90 Accepted 7ms 324.0 KiB
#91 Accepted 11ms 444.0 KiB
#92 Accepted 11ms 568.0 KiB
#93 Accepted 6ms 576.0 KiB
#94 Accepted 6ms 532.0 KiB
#95 Accepted 7ms 576.0 KiB
#96 Accepted 5ms 532.0 KiB
#97 Accepted 5ms 532.0 KiB
#98 Accepted 5ms 560.0 KiB
#99 Accepted 5ms 532.0 KiB
#100 Accepted 5ms 536.0 KiB

Code

#include <iostream>
#include <vector>
#include <cmath>
#include <numeric>
#include <algorithm>
#include <set>
#include <unordered_set>
#include <cstring>
#include <unordered_map>
#include <iomanip>
#include <queue>
#include <map>
#include <sstream>
#include <stack>
#include <bitset>
#include <random>

using ll = long long;

using namespace std;

constexpr int nm = (1 << 9) + 10;
constexpr pair<int, int> dirs[] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};

char a[20][20];
int t[20][20];
int f[nm];

int findCost(int t0, int u, int v) {
    if (t[u][v] <= t0) return 1e9;
    vector<vector<int>> t2(20, vector<int>(20, 1e9));
    t2[u][v] = t0;
    queue<pair<int, int>> q;
    q.emplace(u, v);

    while (q.size()) {
        auto [i, j] = q.front();
        q.pop();

        if (i == 0 || i == 10 || j == 0 || j == 10) return t2[i][j] + 1;

        for (auto [dx, dy]: dirs) {
            int i2 = i + dx, j2 = j + dy;
            if (i2 >= 0 && i2 < 11 && j2 >= 0 && j2 < 11 && t2[i2][j2] > t2[i][j] + 1 && t[i2][j2] > t2[i][j] + 1) {
                t2[i2][j2] = t2[i][j] + 1;
                q.emplace(i2, j2);
            }
        }
    }
    return 1e9;
}

int main() {
    #ifdef LOCAL
    freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);
    #endif
    ios::sync_with_stdio(0);
    cin.tie(0);

    vector<pair<int, int>> people;
    vector<pair<int, int>> fire;
    memset(t, 0x3f, sizeof(t));
    queue<pair<int, int>> q;
    for (int i = 0; i < 11; ++i) {
        for (int j = 0; j < 11; ++j) {
            cin >> a[i][j];
            if (a[i][j] == 'P') people.emplace_back(i, j);
            else if (a[i][j] == 'F') {
                fire.emplace_back(i, j);
                t[i][j] = 0;
                q.emplace(i, j);
            }
        }
    }

    while (q.size()) {
        auto [i, j] = q.front();
        q.pop();
        for (auto [dx, dy]: dirs) {
            int i2 = i + dx, j2 = j + dy;
            if (i2 >= 0 && i2 < 11 && j2 >= 0 && j2 < 11 && t[i2][j2] > t[i][j] + 1) {
                t[i2][j2] = t[i][j] + 1;
                q.emplace(i2, j2);
            }
        }
    }

    // for (int i = 0; i < 11; ++i) {
    //     for (int j = 0; j < 11; ++j) {
    //         cout << t[i][j] << " ";
    //     }
    //     cout << "\n";
    // }

    priority_queue<pair<int, int>> pq;
    memset(f, 0x3f, sizeof(f));
    f[0] = 0;
    pq.emplace(0, 0);

    int n = people.size();
    int res = 0;

    while (pq.size()) {
        auto [fmask, mask] = pq.top();
        pq.pop();
        if (fmask != -f[mask]) continue;

        // cout << mask << " " << f[mask] << "\n";
        res = max(res, __builtin_popcount(mask));

        for (int i = 0; i < n; ++i) {
            if ((mask >> i) & 1) continue;
            int cost = findCost(f[mask], people[i].first, people[i].second);
            // cout << "try " << people[i].first << " " << people[i].second << " " << cost << "\n";
            if (cost >= 1e9) continue;
            int mask2 = mask | (1 << i);
            if (f[mask2] > cost) {
                f[mask2] = cost;
                pq.emplace(-f[mask2], mask2);
            }
        }
    }

    cout << res << "\n";
}

Information

Submit By
Type
Submission
Problem
P1221 G. Nine-eleven
Contest
Happy New Year 2026
Language
C++17 (G++ 13.2.0)
Submit At
2026-01-06 16:41:33
Judged At
2026-01-06 16:41:33
Judged By
Score
100
Total Time
11ms
Peak Memory
764.0 KiB