제출 #1358896

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1358896		lenarusw	Bitaro’s Party (JOI18_bitaro)	C++20	100 / 100	1277 ms	147772 KiB

bitaro

#include <bits/stdc++.h>

using namespace std;

using ull = unsigned long long;
using ll = long long;
using ld = long double;

// #pragma GCC target("avx2")
// #pragma GCC optimize("O3")
// #pragma GCC optimize("unroll-loops")

// #define int long long

constexpr int N = 1'000'00, c = 100;

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/hash_policy.hpp>
using namespace __gnu_pbds;
struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        // http://xorshift.di.unimi.it/splitmix64.c
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};

vector<int> g[N];
bool used[N];

vector<pair<int, int>> dsts[N];
void dfs(int v) {
    used[v] = true;
    vector<pair<int, int>> elems;
    elems.emplace_back(0, v);
    for (int to : g[v]) {
        if (!used[to]) {
            dfs(to);
        }
        for (auto el : dsts[to]) {
            elems.emplace_back(el.first + 1, el.second);
        }
    }
    sort(elems.rbegin(), elems.rend());
    gp_hash_table<int, null_type, custom_hash> was;
    for (auto [d, u] : elems) {
        if (dsts[v].size() > c) break;
        if (was.find(u) == was.end()) {
            dsts[v].emplace_back(d, u);
            was.insert(u);
        }
    }
}

inline void solve() {
    int n, m, q;
    cin >> n >> m >> q;
    for (int i = 0; i < m; i++) {
        int s, e;
        cin >> s >> e;
        s--;
        e--;
        g[e].push_back(s);
    }
    for (int i = 0; i < n; i++) {
        if (!used[i]) dfs(i);
    }
    for (int i = 0; i < q; i++) {
        int t, k;
        cin >> t >> k;
        t--;
        if (k > c) {
            vector<int> dp(t + 1, -1e9);
            vector<bool> can(t + 1, true);
            for (int i = 0; i < k; i++) {
                int c;
                cin >> c;
                c--;
                if (c > t) continue;
                can[c] = false;
            }
            for (int i = 0; i < t + 1; i++) {
                if (can[i]) {
                    dp[i] = 0;
                }

                for (int to : g[i]) {
                    if (dp[to] == -1e9) continue;
                    dp[i] = max(dp[i], dp[to] + 1);
                }
            }
            cout << (dp.back() == -1e9 ? -1 : dp.back()) << "\n";
            continue;
        }
        gp_hash_table<int, null_type, custom_hash> els;
        for (int i = 0; i < k; i++) {
            int c;
            cin >> c;
            c--;
            els.insert(c);
        }
        int ans = -1;
        for (auto [d, v] : dsts[t]) {
            if (els.find(v) == els.end()) {
                ans = d;
                break;
            }
        }
        cout << ans << "\n";
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1;
    // cin >> t;
    while (t--) solve();
    return 0;
}

• 서브태스크 1: 7 / 7
• 서브태스크 2: 7 / 7
• 서브태스크 3: 86 / 86