Submission #520109

#	Time	Username	Problem	Language	Result	Execution time	Memory
520109		Hau	Bitaro’s Party (JOI18_bitaro)	C++17	100 / 100	784 ms	214504 KiB

bitaro

#include <bits/stdc++.h>

#define fi first
#define se second
#define For(i, a, b) for (int i=a;i<=b;++i)
#define Ford(i, a, b) for(int i=a;i>=b;--i)

using namespace std;

typedef long long ll;
typedef pair<int, int> ii;
typedef array<int, 3> arr;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<ii> vii;

const int N = 2 * 1e5 + 5;
const int B = 177;

int f[N];
int vis[N], ver = 0;

void merge(vii &a, vii &b) {
    ver++;
    int n = a.size(), m = b.size();
    int i = 0, j = 0, s = min(n + m, B);
    static ii c[N];
    int k = 0;
    while (k < s) {
        if (i >= n || (j < m && b[j].se + 1 > a[i].se)) {
            if (vis[b[j].fi] != ver) {
                c[++k] = {b[j].fi, b[j].se + 1};
                vis[b[j].fi] = ver;
            }
            j++;
        }
        else {
            if (vis[a[i].fi] != ver) {
                c[++k] = a[i];
                vis[a[i].fi] = ver;
            }
            i++;
        }
        if (i >= n && j >= m) break;
    }
    For(i, 0, n - 1) a[i] = c[i + 1];
    For(i, n + 1, k) a.push_back(c[i]);
}

void solve()
{
    int n, m, q;
    cin >> n >> m >> q;
    vector<vi> pre(n + 5);
    For(i, 1, m) {
        int u, v; cin >> u >> v;
        pre[v].push_back(u);
    }

    vector<vii> good(n + 5);
    For(i, 1, n) {
        good[i].push_back({i, 0});
        for (int j : pre[i]) {
            merge(good[i], good[j]);
        }
    }

    while (q--) {
        int u; cin >> u;
        ver++;

        int y; cin >> y;
        int cnt = 0;
        For(i, 1, y) {
            int x; cin >> x;
            vis[x] = ver;
        }

        if (y < B) {
            int ans = -1;
            for (ii i : good[u]) if (vis[i.fi] != ver) {
                ans = i.se;
                break;
            }
            cout << ans << "\n";
        }
        else {
            For(i, 1, u) {
                if (vis[i] == ver) f[i] = -1;
                else f[i] = 0;
                for (int j : pre[i]) if (f[j] != -1)
                    f[i] = max(f[i], f[j] + 1);
            }
            cout << f[u] << "\n";
        }
    }
}

int main()
{
	// freopen("input.txt","r",stdin);
	// freopen("output.txt","w",stdout);

	ios_base::sync_with_stdio(false);
	cin.tie(NULL);cout.tie(NULL);

	solve();

    // cerr << 1.0 * clock() / CLOCKS_PER_SEC;

	return 0;
}

Compilation message (stderr)

bitaro.cpp: In function 'void solve()':
bitaro.cpp:73:13: warning: unused variable 'cnt' [-Wunused-variable]
   73 |         int cnt = 0;
      |             ^~~

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