Submission #70434612

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define int ll
mt19937 rng(0);
vector<int> v[200020];
string s;
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int N, M;
    cin >> N >> M;
    for (int i = 0; i < M; i++) {
        int a, b;
        cin >> a >> b;
        a--;
        b--;
        v[a].push_back(b);
        v[b].push_back(a);
    }
    cin >> s;
    vector<pair<int, int>> d1(N, {-1, -1}), d2(N, {-1, -1});
    queue<array<int, 3>> q;
    for (int i = 0; i < N; i++) {
        if (s[i] == 'S') {
            q.push({0, i, i});
        }
    }
    while (!q.empty()) {
        auto [d, pos, start] = q.front();
        q.pop();
        bool d11 = d1[pos].first != -1;
        bool d22 = d2[pos].first != -1;
        if (d11 && d22) continue;
        if (!d11) {
            d1[pos] = {d, start};
        }
        if (d11 && d1[pos].second == start) continue;
        if (d11) d2[pos] = {d, start};
        for (auto x : v[pos]) q.push({d + 1, x, start});
    }
    for (int i = 0; i < N; i++) {
        if (s[i] == 'D') {
            cout << d1[i].first + d2[i].first << "\n";
        }
    }
}

Submission Info

Submission Time
Task E - Hit and Away
User davi_bart
Language C++ 20 (gcc 12.2)
Score 450
Code Size 1194 Byte
Status AC
Exec Time 136 ms
Memory 34128 KiB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 450 / 450
Status
AC × 2
AC × 54
Set Name Test Cases
Sample example_00.txt, example_01.txt
All example_00.txt, example_01.txt, hand_00.txt, hand_01.txt, hand_02.txt, hand_03.txt, hand_04.txt, hand_05.txt, hand_06.txt, hand_07.txt, hand_08.txt, hand_09.txt, hand_10.txt, hand_11.txt, hand_12.txt, hand_13.txt, hand_14.txt, hand_15.txt, random_00.txt, random_01.txt, random_02.txt, random_03.txt, random_04.txt, random_05.txt, random_06.txt, random_07.txt, random_08.txt, random_09.txt, random_10.txt, random_11.txt, random_12.txt, random_13.txt, random_14.txt, random_15.txt, random_16.txt, random_17.txt, random_18.txt, random_19.txt, random_20.txt, random_21.txt, random_22.txt, random_23.txt, random_24.txt, random_25.txt, random_26.txt, random_27.txt, random_28.txt, random_29.txt, random_30.txt, random_31.txt, random_32.txt, random_33.txt, random_34.txt, random_35.txt
Case Name Status Exec Time Memory
example_00.txt AC 2 ms 3432 KiB
example_01.txt AC 2 ms 3444 KiB
hand_00.txt AC 132 ms 20576 KiB
hand_01.txt AC 119 ms 26600 KiB
hand_02.txt AC 111 ms 32732 KiB
hand_03.txt AC 86 ms 34128 KiB
hand_04.txt AC 88 ms 31788 KiB
hand_05.txt AC 34 ms 27616 KiB
hand_06.txt AC 34 ms 27532 KiB
hand_07.txt AC 126 ms 20552 KiB
hand_08.txt AC 72 ms 25384 KiB
hand_09.txt AC 33 ms 21320 KiB
hand_10.txt AC 92 ms 20504 KiB
hand_11.txt AC 95 ms 25288 KiB
hand_12.txt AC 97 ms 25384 KiB
hand_13.txt AC 88 ms 30296 KiB
hand_14.txt AC 78 ms 34088 KiB
hand_15.txt AC 81 ms 34096 KiB
random_00.txt AC 119 ms 24464 KiB
random_01.txt AC 116 ms 24100 KiB
random_02.txt AC 108 ms 23900 KiB
random_03.txt AC 122 ms 24100 KiB
random_04.txt AC 121 ms 24160 KiB
random_05.txt AC 117 ms 23920 KiB
random_06.txt AC 123 ms 21208 KiB
random_07.txt AC 127 ms 21732 KiB
random_08.txt AC 123 ms 22704 KiB
random_09.txt AC 136 ms 20996 KiB
random_10.txt AC 133 ms 21264 KiB
random_11.txt AC 125 ms 23392 KiB
random_12.txt AC 122 ms 21140 KiB
random_13.txt AC 124 ms 21688 KiB
random_14.txt AC 122 ms 22704 KiB
random_15.txt AC 107 ms 20928 KiB
random_16.txt AC 114 ms 21916 KiB
random_17.txt AC 103 ms 21756 KiB
random_18.txt AC 19 ms 16084 KiB
random_19.txt AC 24 ms 19056 KiB
random_20.txt AC 27 ms 22672 KiB
random_21.txt AC 28 ms 22856 KiB
random_22.txt AC 25 ms 20644 KiB
random_23.txt AC 20 ms 17096 KiB
random_24.txt AC 51 ms 25816 KiB
random_25.txt AC 47 ms 26872 KiB
random_26.txt AC 48 ms 26240 KiB
random_27.txt AC 47 ms 27384 KiB
random_28.txt AC 55 ms 26116 KiB
random_29.txt AC 49 ms 26660 KiB
random_30.txt AC 104 ms 24192 KiB
random_31.txt AC 77 ms 29764 KiB
random_32.txt AC 85 ms 24736 KiB
random_33.txt AC 99 ms 33196 KiB
random_34.txt AC 81 ms 23740 KiB
random_35.txt AC 81 ms 27960 KiB