Submission #526610

#	Time	Username	Problem	Language	Result	Execution time	Memory
526610		Aldas25	Bitaro’s Party (JOI18_bitaro)	C++14	100 / 100	1482 ms	414912 KiB

bitaro

#include <bits/stdc++.h>

using namespace std;

#define FAST_IO ios_base::sync_with_stdio(0); cin.tie(0)
#define FOR(i, a, b) for(int i = (a); i <= (b); i++)
#define REP(n) FOR(O, 1, (n))
#define pb push_back
#define f first
#define s second
typedef long double ld;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pii> vii;
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int MAXN = 100100, MAXK = 40;
const int INF = 1e9;
//const ll MOD = 1e9+7;
//const ll MOD = 998244353;

const int C = 300;
//const int C = 0;

int n, m, q;
vi adj[MAXN];
bool busy[MAXN];
vi busySeq;
int dp[MAXN];
vii pre[MAXN];
//priority_queue<pii, vii, greater<pii>> pq[MAXN];
//vii tmp;

/*void clean (int id) {
    while (pq[id].size() > C) {
        pq[id].pop();
    }
}

void save (int id) {
    while (!pq[id].empty()) {
        auto p = pq[id].top();
        pre[id].pb(p);
        pq[id].pop();
    }
    reverse(pre[id].begin(), pre[id].end());
}*/

vii tmp;
bool added[MAXN];
vi tmpAdded;

void pass (int a, int b) {
    tmp.clear();

    tmpAdded.clear();

    int id1 = 0, id2 = 0;
    while (id1 < (int)pre[a].size() || id2 < (int)pre[b].size()) {
        if ((int)tmp.size() > C) break;

        if ( (id2 >= (int)pre[b].size()) ||
            (id1 < (int)pre[a].size() && pre[a][id1].f+1 > pre[b][id2].f) ) {
                int from = pre[a][id1].s;

                if (!added[from]) {
                    tmp.pb({pre[a][id1].f+1, pre[a][id1].s});
                    added[from] = true;
                    tmpAdded.pb(from);
                }
                id1++;
            } else  {
                int from = pre[b][id2].s;

                if (!added[from]) {
                    added[from] = true;
                    tmpAdded.pb(from);
                    tmp.pb(pre[b][id2]);
                }
                id2++;
            }
    }

    swap(pre[b], tmp);

    for (int x : tmpAdded) added[x] = false;
}

int main()
{
    FAST_IO;

    cin >> n >> m >> q;
    REP(m) {
        int s, e;
        cin >> s >> e;
        adj[s].pb(e);
    }

    FOR(i, 1, n) {
        //pq[i].push({0, i});
        //clean(i);
        //save(i);
        pre[i].pb({0, i});

        for (int u : adj[i])
            pass (i, u);
    }

    REP(q) {
        int t, y;
        cin >> t >> y;

        busySeq.clear();
        REP(y) {
            int x; cin >> x;
            busySeq.pb(x);
            busy[x] = true;
        }

        if (y >= C) {
            FOR(i, 1, t) dp[i] = busy[i] ? (-1) : 0;

            FOR(i, 1, t) {
                if (dp[i] < 0) continue;
                for (int u : adj[i])
                    dp[u] = max(dp[u], dp[i] + 1);
            }

            cout << dp[t] << "\n";
        } else {
            int ans = -1;
            for (auto p : pre[t]) {
                int len = p.f, from = p.s;
                if (busy[from]) continue;
                ans = len;
                break;
            }
            cout << ans << "\n";
        }


        for (int x : busySeq) busy[x] = false;

    }

    return 0;
}

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