Submission #1134596

#	Time	Username	Problem	Language	Result	Execution time	Memory
1134596		gyg	Bitaro’s Party (JOI18_bitaro)	C++20	100 / 100	1069 ms	417504 KiB

bitaro

#include <bits/stdc++.h>
using namespace std;
#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 = 2e9;

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

arr<vec<pii>, N> dp;
vec<int> id;
arr<int, N> usd;
vec<int> usd_lst;
void prcmp() {
    for (int u = 1; u <= n; u++) {
        id.clear();
        id.resize(in[u].size());

        usd_lst.clear();
        for (int i = 1; i <= k; i++) {
            pii bst = {-1, u};
            for (int j = 0; j < in[u].size(); j++) {
                int v = in[u][j];
                while (id[j] != dp[v].size() && usd[dp[v][id[j]].sec]) 
                    id[j]++;
                if (id[j] != dp[v].size()) bst = max(bst, dp[v][id[j]]);
            }
            usd_lst.push_back(bst.sec), usd[bst.sec] = true;
            dp[u].push_back({bst.fir + 1, bst.sec});
        }
        for (int v : usd_lst) usd[v] = false;
    }

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

arr<int, N> dlt;
vec<int> dlt_lst;
arr<int, N> pd;
void cmp() {
    dlt_lst.clear();
    int u, x; cin >> u >> x;
    for (int i = 1; i <= x; i++) { int v; cin >> v; dlt_lst.push_back(v), dlt[v] = true; }

    auto fst = [&]() {
        int mx = -1;
        for (pii y : dp[u]) 
            if (!dlt[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[v]) mx = max(mx, pd[v]);
        return mx;
    };
    
    if (x <= k - 5) {
        // cout << u << ": " << fst() << " " << slw() << endl;
        // assert(fst() == slw());
        cout << fst() << '\n';
    } else {
        cout << slw() << '\n';
    }

    for (int v : dlt_lst) dlt[v] = false;
}

signed main() {
    // freopen("in", "r", stdin);
    cin.sync_with_stdio(false), cin.tie(0);
    cin >> n >> m >> q; k = max((int) sqrtl(n), 1);
    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: 7 / 7
• Subtask 3: 86 / 86