Submission #787910

#	Time	Username	Problem	Language	Result	Execution time	Memory
787910		AmirAli_H1	Bitaro’s Party (JOI18_bitaro)	C++17	100 / 100	1577 ms	180232 KiB

bitaro

// In the name of Allah
#include <bits/stdc++.h>
using namespace std;

typedef		long long				ll;
typedef		pair<int, int>			pii;
typedef		pair<ll, ll>			pll;

#define		endl					'\n'
#define		sep						' '
#define		all(x)					(x).begin(),(x).end()
#define		len(x)					((ll) (x).size())
#define		pb						push_back
#define		Mp						make_pair
#define		F						first
#define		S						second

int n, m, q;
const int maxn = 2e5 + 4;
const int sq = 100, oo = 1e9;
vector<int> adj[maxn], adjr[maxn];
int ans[maxn], res[maxn], val[maxn]; vector<int> A[maxn], vc;
vector<pii> dp[maxn]; bool M[maxn];

void solve(int R) {
    fill(res, res + R, 0);
    for (int v = 0; v < R; v++) {
        for (int u : adjr[v]) {
            res[v] = max(res[v], res[u] + 1);
        }
        if (M[v] && res[v] == 0) res[v] = -oo;
    }
}

bool cmp(pii a, pii b) {
    if (a.S != b.S) return a.S > b.S;
    else return a.F > b.F;
}

int main() {
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    cin >> n >> m >> q;
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v; u--; v--;
        adj[u].pb(v); adjr[v].pb(u);
    }

    fill(val, val + n, -1);
    for (int v = 0; v < n; v++) {
        vc.clear();

        vc.pb(v);
        val[v] = 0;
        for (int u : adjr[v]) {
            for (auto f : dp[u]) {
                vc.pb(f.S);
                val[f.S] = max(val[f.S], f.F + 1);
            }
        }
        sort(all(vc)); vc.resize(unique(all(vc)) - vc.begin());

        for (int u : vc) {
            dp[v].pb(Mp(val[u], u));
            val[u] = -1;
        }

        sort(all(dp[v]), greater<pii>()); dp[v].resize(min(sq + 10ll, len(dp[v])));
    }

    for (int i = 0; i < q; i++) {
        int v, T;
        cin >> v >> T; v--;

        for (int j = 0; j < T; j++) {
            int u;
            cin >> u; u--;
            if (u <= v) {
                A[i].pb(u);
                M[u] = 1;
            }
        }

        if (T < sq) {
            ans[i] = -1;
            for (auto f : dp[v]) {
                int u = f.S, val = f.F;
                if (!M[u]) {
                    ans[i] = val;
                    break;
                }
            }
        }
        else {
            solve(v + 1);
            if (res[v] >= 0) ans[i] = res[v];
            else ans[i] = -1;
        }

        for (int u : A[i]) M[u] = 0;
    }

    for (int i = 0; i < q; i++) cout << ans[i] << endl;

	return 0;
}

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