Submission #724355

#	Time	Username	Problem	Language	Result	Execution time	Memory
724355		MISM06	Bitaro’s Party (JOI18_bitaro)	C++17	100 / 100	1297 ms	414580 KiB

bitaro

//0 1 1 0 1
//0 1 0 0 1
//1 0 0 1 1
//0 1 1 0 1
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2")

using namespace std;

#define F 			first
#define S 			second
#define pb 			push_back
#define sze			size()
#define	all(x)		x.begin() , x.end()
#define wall__		cout << "--------------------------------------\n";
#define kids		int mid = (tl + tr) >> 1, cl = v << 1, cr = v << 1 | 1
#define file_io		freopen("input.cpp", "r", stdin); freopen("output.cpp", "w", stdout);

typedef long long ll;
typedef long double dl;
typedef pair < int , int > pii;
typedef pair < int , ll > pil;
typedef pair < ll , int > pli;
typedef pair < ll , ll > pll;
typedef pair < int , pii > piii;
typedef pair < ll, pll > plll;


const ll N = 1e5 + 10;
const ll mod = 1e9 + 7;
const ll inf = 2e16;
const ll rinf = -2e16;
const ll INF = 1e9 + 10;
const ll rINF = -1e9 - 10;
const ll lg = 32;
const ll lm = 320;

int n, m, q, p[N], dp[N];
vector < int > g[N];
vector < pii > sel[N];
bool mark[N];

void solve () {

	cin >> n >> m >> q;
	for (int i = 1; i <= m; i++) {
		int v, u; cin >> v >> u;
		g[u].pb(v);
	}
	sel[0].pb({-1, -1});
	sel[1].pb({0, 1});
	for (int v = 2; v <= n; v++) {
		int c = 0;
		while (c < lm) {
			int mx = 0;
			for (auto u : g[v]) {
				if (p[u] == sel[u].sze) continue;
				if (mark[sel[u][p[u]].S]) ++p[u];
				if (p[u] == sel[u].sze) continue;
				if (sel[mx][p[mx]].F <= sel[u][p[u]].F) mx = u;
			}
			if (mx == 0 && !mark[v]) {
				mark[v] = 1;
				sel[v].pb({0, v});
			}
			else if (mx) {
				sel[v].pb({sel[mx][p[mx]].F + 1, sel[mx][p[mx]].S});
				mark[sel[mx][p[mx]].S] = 1;
				++p[mx];
			}
			++c;
		}
		mark[v] = 0;
		for (auto u : g[v]) p[u] = 0;
		for (auto e : sel[v]) mark[e.S] = 0;
	}
	while (q--) {
		int v, k;
		vector < int > bad;
		cin >> v >> k;
		for (int i = 1; i <= k; i++) {
			int x; cin >> x; bad.pb(x);
			mark[x] = 1;
		}
		if (k < lm) {
			int ans = -1;
			for (auto e : sel[v]) {
				if (!mark[e.S]) {
					ans = e.F;
					break;
				}
			}
			cout << ans << '\n';
		} else {
			for (int i = 1; i <= v; i++) {
				dp[i] = -1;
				for (auto u : g[i]) dp[i] = max(dp[i], dp[u]);
				if (dp[i] >= 0) ++dp[i];
				if (!mark[i]) dp[i] = max(dp[i], 0);
			}
			cout << dp[v] << '\n';
		}	
		for (auto x : bad) mark[x] = 0;
	}

}


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

	int t = 1;
	// cin >> t;
	while (t--) {solve();}
    return 0;
}
/*
*/
//inhonorofsbi;

Compilation message (stderr)

bitaro.cpp: In function 'void solve()':
bitaro.cpp:58:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |     if (p[u] == sel[u].sze) continue;
      |              ^
bitaro.cpp:60:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |     if (p[u] == sel[u].sze) continue;
      |              ^

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