Submission #1134284

#	Time	Username	Problem	Language	Result	Execution time	Memory
1134284		gyg	Bitaro’s Party (JOI18_bitaro)	C++20	7 / 100	2081 ms	461840 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> out, 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';
    // }
}

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

    auto fst = [&]() {
        int mx = -1;
        for (pii y : dp[u]) 
            if (!dlt.count(y.sec))
                mx = max(mx, y.fir);
        return mx;
    };
    auto slw = [&]() {
        pd.fill(-INF);
        pd[u] = 0;
        for (int v = u - 1; v >= 1; v--)
            for (int w : out[v])
                pd[v] = max(pd[v], pd[w] + 1);
        
        int mx = -1;
        for (int v = 1; v <= n; v++)
            if (!dlt.count(v) && pd[v] >= 0) mx = max(mx, pd[v]);
        return mx;
    };
    
    if (x <= k) {
        // cout << u << ": " << fst() << " " << slw() << endl;
        assert(fst() == slw());
        cout << fst() << '\n';
    } else {
        cout << slw() << '\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;
        out[u].push_back(v), in[v].push_back(u);
    }

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

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