Submission #70469789

---

Source Code Expand

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <deque>
#include <queue>
#include <numeric>
#include <stack>
#include <cassert>
#include <cstring>
#include <cmath>
#include <random>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <chrono>
#include <sstream>
#include <limits>
#include <functional>
using namespace std;
#define endl '\n'
// #define LOCAL

using int64 = int64_t;
using uint64 = unsigned long long;
using int128 = __int128_t;

#ifdef LOCAL
#include "src/debug.h"
#else
#define debug(...) 42
#endif

int N, M;
vector<vector<int>> adj;
string S;

vector<int64> bfs(int src) {
    vector<int64> ans(N, 0);
    vector<vector<int>> vis(N, vector<int>(2, -1));
    queue<pair<int, int>> q;
    for (int i = 0; i < N; ++i) {
        if (S[i] == 'S') {
            q.emplace(i, i);
        }
    }
    int steps = 0;
    while (!q.empty()) {
        int sz = q.size();
        for (int i = 0; i < sz; ++i) {
            auto [u, src] = q.front();
            if (S[u] == 'D') ans[u] += steps;
            // cout << "At node " << u << " from source " << src << " at step " << steps << endl;
            q.pop();
            for (int v : adj[u]) {
                if (vis[v][0] == src || vis[v][1] == src) continue;
                if (vis[v][0] == -1) {
                    vis[v][0] = src;
                    q.emplace(v, src);
                } else if (vis[v][1] == -1) {
                    vis[v][1] = src;
                    q.emplace(v, src);
                }
            }
        }
        steps++;
    }
    return ans;
}

void solve() {
    cin >> N >> M;
    adj.assign(N, vector<int>());
    for (int i = 0; i < M; ++i) {
        int u, v;
        cin >> u >> v;
        --u, --v;
        adj[u].emplace_back(v);
        adj[v].emplace_back(u);
    }
    cin >> S;
    vector<int64> ans = bfs(0);
    for (int64 x : ans) {
        if (!x) continue;
        cout << x << endl;
    }
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    solve();
    return 0;
}

Submission Info

Compile Error

Main.cpp: In function ‘std::vector<long int> bfs(int)’:
Main.cpp:39:23: warning: unused parameter ‘src’ [-Wunused-parameter]
   39 | vector<int64> bfs(int src) {
      |                   ~~~~^~~

Judge Result