Test/UC/3-36-F.test.cpp

View this file on GitHub
Last update: 2025-05-11 14:10:45+09:00
Problem: https://onlinejudge.u-aizu.ac.jp/courses/lesson/2/ITP1/1/ITP1_1_A
Link: https://contest.ucup.ac/contest/2021/problem/10728
Link: https://contest.ucup.ac/submission/1046445

Depends on

Code

// #define PROBLEM "https://contest.ucup.ac/contest/2021/problem/10728"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/lesson/2/ITP1/1/ITP1_1_A"

/*
 * The 3rd Universal Cup. Stage 36: Wulin F. Challenge NPC III
 * https://contest.ucup.ac/submission/1046445
 */

#include "../../Src/Utility/SeparatedFamilySet.hpp"

#include <iostream>
#include <vector>
int N, M, K, C[100010];
std::vector<int> g[100010];
int solve() {
    std::vector<std::vector<int>> col(50);
    for (int i = 0 ; i < N ; i++) col[C[i]].push_back(i);
    for (int t = 0 ; t < 50 ; t++) {
        for (const std::vector<bool>& s : zawa::SeparatedFamilySet(col[t].size())) {
            const int INF = (int)1e9;
            std::vector<int> que, dist(N, INF);
            for (int i = 0 ; i < std::ssize(col[t]) ; i++) if (s[i]) {
                dist[col[t][i]] = 0;
                que.push_back(col[t][i]);
            }
            for (int qt = 0 ; qt < std::ssize(que) ; qt++) {
                const int v = que[qt];
                for (int x : g[v]) if (dist[x] == INF) {
                    dist[x] = dist[v] + 1;
                    que.push_back(x);
                }
            }
            int min = INF;
            for (int i = 0 ; i < std::ssize(col[t]) ; i++) if (!s[i]) {
                min = std::min(min, dist[col[t][i]]);
            }
            if (min + 1 <= K) return false;
        } 
    }
    return true;
}
int main() {
#ifdef ONLINE_JUDGE
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    std::ios::sync_with_stdio(false);
    int T;
    std::cin >> T;
    while (T--) {
        std::cin >> N >> M >> K;
        for (int i = 0 ; i < N ; i++) {
            std::cin >> C[i];
            C[i]--;
        }
        for (int i = 0 ; i < N ; i++) g[i].clear();
        for (int i = 0 ; i < M ; i++) {
            int u, v;
            std::cin >> u >> v;
            u--; v--;
            g[u].push_back(v);
        }
        std::cout << (solve() ? "YES\n" : "NO\n");
    }
#else
    std::cout << "Hello World\n";
#endif
}

#line 1 "Test/UC/3-36-F.test.cpp"
// #define PROBLEM "https://contest.ucup.ac/contest/2021/problem/10728"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/lesson/2/ITP1/1/ITP1_1_A"

/*
 * The 3rd Universal Cup. Stage 36: Wulin F. Challenge NPC III
 * https://contest.ucup.ac/submission/1046445
 */

#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
// 向きのついた分割
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 10 "Test/UC/3-36-F.test.cpp"

#include <iostream>
#line 13 "Test/UC/3-36-F.test.cpp"
int N, M, K, C[100010];
std::vector<int> g[100010];
int solve() {
    std::vector<std::vector<int>> col(50);
    for (int i = 0 ; i < N ; i++) col[C[i]].push_back(i);
    for (int t = 0 ; t < 50 ; t++) {
        for (const std::vector<bool>& s : zawa::SeparatedFamilySet(col[t].size())) {
            const int INF = (int)1e9;
            std::vector<int> que, dist(N, INF);
            for (int i = 0 ; i < std::ssize(col[t]) ; i++) if (s[i]) {
                dist[col[t][i]] = 0;
                que.push_back(col[t][i]);
            }
            for (int qt = 0 ; qt < std::ssize(que) ; qt++) {
                const int v = que[qt];
                for (int x : g[v]) if (dist[x] == INF) {
                    dist[x] = dist[v] + 1;
                    que.push_back(x);
                }
            }
            int min = INF;
            for (int i = 0 ; i < std::ssize(col[t]) ; i++) if (!s[i]) {
                min = std::min(min, dist[col[t][i]]);
            }
            if (min + 1 <= K) return false;
        } 
    }
    return true;
}
int main() {
#ifdef ONLINE_JUDGE
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    std::ios::sync_with_stdio(false);
    int T;
    std::cin >> T;
    while (T--) {
        std::cin >> N >> M >> K;
        for (int i = 0 ; i < N ; i++) {
            std::cin >> C[i];
            C[i]--;
        }
        for (int i = 0 ; i < N ; i++) g[i].clear();
        for (int i = 0 ; i < M ; i++) {
            int u, v;
            std::cin >> u >> v;
            u--; v--;
            g[u].push_back(v);
        }
        std::cout << (solve() ? "YES\n" : "NO\n");
    }
#else
    std::cout << "Hello World\n";
#endif
}