제출 #1134273

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1134273		gyg	Bitaro’s Party (JOI18_bitaro)	C++20	0 / 100	38 ms	71080 KiB

bitaro

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define arr array
#define vec vector 
#define deq deque
#define pii pair<int, int>
#define fir first
#define sec second
#define hset unordered_set
const int N = 1e5 + 5, INF = 1e12;

int n, m, q, k;
arr<vec<int>, N> in;

arr<deq<pii>, N> dp;
void prcmp() {
    for (int u = 1; u <= n; u++) {
        vec<deq<pii>> trns;
        for (int v : in[u]) trns.push_back(dp[v]);

        hset<int> usd;
        for (int i = 1; i <= k; i++) {
            pii bst = {-1, u};
            for (int j = 0; j < trns.size(); j++) {
                while (trns[j].size() && usd.count(trns[j].front().sec)) 
                    trns[j].pop_front();
                if (trns[j].size()) bst = max(bst, trns[j].front());
            }
            usd.insert(bst.sec);
            dp[u].push_back({bst.fir + 1, bst.sec});
        }
    }

    // for (int u = 1; u <= n; u++) {
    //     cout << u << ": ";
    //     for (pii x : dp[u]) cout << x.fir << " " << x.sec << "  ";
    //     cout << '\n';
    // }
}

arr<int, N> dst;
arr<bool, N> vs;
queue<int> ord;
void bfs(int st) {
    dst.fill(INF), vs.fill(false);
    dst[st] = 0, ord.push(st);
    while (ord.size()) {
        int u = ord.back(); ord.pop();
        if (vs[u]) continue;
        vs[u] = true;
        for (int v : in[u]) {
            int nw_dst = dst[u] + 1;
            if (nw_dst >= dst[v]) continue;
            dst[v] = nw_dst, ord.push(v);
        }
    }
}

hset<int> dlt;
void cmp() {
    dlt.clear();
    int u, x; cin >> u >> x;
    for (int i = 1; i <= x; i++) { int v; cin >> v; dlt.insert(v); }

    if (x <= k) {
        int mx = -1;
        for (pii y : dp[u]) 
            if (!dlt.count(y.sec))
                mx = max(mx, y.fir);
        cout << mx << '\n';
    } else {
        bfs(u);
        int mx = -1;
        for (int v = 1; v <= n; v++)
            if (!dlt.count(v) && vs[v]) mx = max(mx, dst[v]);
        cout << mx << '\n'; 
    }
}

signed main() {
    // freopen("in", "r", stdin);
    cin.sync_with_stdio(false), cin.tie(0);
    cin >> n >> m >> q; k = max((int) sqrtl(n), 1ll);
    for (int i = 1; i <= m; i++) {
        int u, v; cin >> u >> v;
        in[v].push_back(u);
    }

    prcmp();
    for (int i = 1; i <= q; i++) cmp();
}

• Subtask 1: 0 / 7
• Subtask 2: 0 / 7
• Subtask 3: 0 / 86