cp-documentation

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub zawa-tin/cp-documentation

:heavy_check_mark: Test/AtCoder/abc429_e.test.cpp

Depends on

Code

// #define PROBLEM "https://atcoder.jp/contests/abc429/tasks/abc429_e"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/lesson/2/ITP1/1/ITP1_1_A"
#include "../../Src/Utility/SeparatedFamilySet.hpp"
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;
void solve() {
    int N, M;
    cin >> N >> M;
    vector<vector<int>> g(N);
    for (int i = 0 ; i < M ; i++) {
        int a, b;
        cin >> a >> b;
        a--; b--;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    string S;
    cin >> S;
    vector<int> safe, danger;
    for (int i = 0 ; i < N ; i++) {
        if (S[i] == 'S')
            safe.push_back(i);
        else
            danger.push_back(i);
    }
    const int INF = (int)1e9;
    auto bfs = [&](const vector<bool>& use) -> vector<int> {
        vector<int> dist(N, INF), que;
        for (int i = 0 ; i < ssize(safe) ; i++)
            if (use[i]) {
                dist[safe[i]] = 0;
                que.push_back(safe[i]);
            }
        for (int t = 0 ; t < ssize(que) ; t++) {
            const int v = que[t];
            for (int x : g[v])
                if (dist[x] == INF) {
                    dist[x] = dist[v] + 1;
                    que.push_back(x);
                }
        }
        return dist;
    };
    vector<int> ans(N, INF);
    for (vector<bool> sep : zawa::SeparatedFamilySet(safe.size())) {
        vector<int> da = bfs(sep);
        for (int i = 0 ; i < ssize(sep) ; i++)
            sep[i] = !sep[i];
        vector<int> db = bfs(sep);
        for (int i : danger)
            ans[i] = min(ans[i], da[i] + db[i]);
    }
    for (int i : danger)
        cout << ans[i] << '\n';
}
int main() {
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);
#ifdef ATCODER
    solve();
#else
    cout << "Hello World\n";
#endif
}
#line 1 "Test/AtCoder/abc429_e.test.cpp"
// #define PROBLEM "https://atcoder.jp/contests/abc429/tasks/abc429_e"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/lesson/2/ITP1/1/ITP1_1_A"
#line 2 "Src/Utility/SeparatedFamilySet.hpp"

#include <algorithm>
#include <vector>
#include <concepts>
#include <ranges>

#line 2 "Src/Template/TypeAlias.hpp"

#include <cstdint>
#include <cstddef>

namespace zawa {

using i16 = std::int16_t;
using i32 = std::int32_t;
using i64 = std::int64_t;
using i128 = __int128_t;

using u8 = std::uint8_t;
using u16 = std::uint16_t;
using u32 = std::uint32_t;
using u64 = std::uint64_t;

using usize = std::size_t;

} // namespace zawa
#line 9 "Src/Utility/SeparatedFamilySet.hpp"

namespace zawa {

// https://noshi91.hatenablog.com/entry/2024/05/31/012055
// each (i, j) satisfy there are k such that res[k][i]=1,res[k][j]=0
std::vector<std::vector<bool>> SeparatedFamilySet(usize U) {
    const usize d = [&]() {
        for (usize i = 1 ; ; i++) {
            usize max = 1;
            for (usize j = 0 ; j < (i / 2) ; j++) {
                max *= i - j;
                max /= j + 1;
            }
            if (max >= U) return i;
        }
        return U;
    }();
    std::vector res(d, std::vector<bool>(U));
    std::vector<u8> in(d);
    std::fill(in.rbegin(), in.rbegin() + d / 2, true);
    for (usize idx = 0 ; idx < U ; idx++) {
        for (usize i = 0 ; i < d ; i++) if (in[i]) {
            res[i][idx] = true;
        }
        std::ranges::next_permutation(in);
    }
    return res;
}

} // namespace zawa
#line 4 "Test/AtCoder/abc429_e.test.cpp"
#include <iostream>
#line 7 "Test/AtCoder/abc429_e.test.cpp"
#include <string>
using namespace std;
void solve() {
    int N, M;
    cin >> N >> M;
    vector<vector<int>> g(N);
    for (int i = 0 ; i < M ; i++) {
        int a, b;
        cin >> a >> b;
        a--; b--;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    string S;
    cin >> S;
    vector<int> safe, danger;
    for (int i = 0 ; i < N ; i++) {
        if (S[i] == 'S')
            safe.push_back(i);
        else
            danger.push_back(i);
    }
    const int INF = (int)1e9;
    auto bfs = [&](const vector<bool>& use) -> vector<int> {
        vector<int> dist(N, INF), que;
        for (int i = 0 ; i < ssize(safe) ; i++)
            if (use[i]) {
                dist[safe[i]] = 0;
                que.push_back(safe[i]);
            }
        for (int t = 0 ; t < ssize(que) ; t++) {
            const int v = que[t];
            for (int x : g[v])
                if (dist[x] == INF) {
                    dist[x] = dist[v] + 1;
                    que.push_back(x);
                }
        }
        return dist;
    };
    vector<int> ans(N, INF);
    for (vector<bool> sep : zawa::SeparatedFamilySet(safe.size())) {
        vector<int> da = bfs(sep);
        for (int i = 0 ; i < ssize(sep) ; i++)
            sep[i] = !sep[i];
        vector<int> db = bfs(sep);
        for (int i : danger)
            ans[i] = min(ans[i], da[i] + db[i]);
    }
    for (int i : danger)
        cout << ans[i] << '\n';
}
int main() {
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);
#ifdef ATCODER
    solve();
#else
    cout << "Hello World\n";
#endif
}
Back to top page