Submission #377551

#	Time	Username	Problem	Language	Result	Execution time	Memory
377551		cheissmart	Bitaro’s Party (JOI18_bitaro)	C++14	100 / 100	1999 ms	423960 KiB

bitaro

#include <bits/stdc++.h>
#define IO_OP std::ios::sync_with_stdio(0); std::cin.tie(0);
#define F first
#define S second
#define V vector
#define PB push_back
#define MP make_pair
#define EB emplace_back
#define ALL(v) (v).begin(), (v).end()
#define debug(x) cerr << "Line(" << __LINE__ << ") -> " << #x << " is " << x << endl

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef V<int> vi;

const int INF = 1e9 + 7, N = 1e5 + 7;

vi G[N]; // from
V<pi> who[N];
int vis[N];
int n, m, q, k;

void dfs(int u) {
	vis[u] = 1;
	who[u].EB(0, u);
	for(int v:G[u]) {
		if(!vis[v]) dfs(v);
		V<pi> tt = who[v], ttt = who[u];
		for(pi& i:tt) i.F--;
		who[u].resize(tt.size() + ttt.size());
		int top = 0;
		//unordered_set<int> s;
		bitset<100001> s;
		for(int i = 0, j = 0; i < int(tt.size()) || j < int(ttt.size());) {
			auto add = [&] (pi& p) {
				// if(s.count(p.S) == 0) {
				if(s[p.S] == 0) {
					// s.insert(p.S);
					s[p.S] = 1;
					who[u][top++] = p;
				}
			};
			if(j == int(ttt.size()) || (i < int(tt.size()) && tt[i].F < ttt[j].F)) {
				add(tt[i++]);
			} else {
				add(ttt[j++]);
			}
		}
		who[u].resize(top);
		if(int(who[u].size()) > k) who[u].resize(k);
	}
}

int no[N];

signed main()
{
	IO_OP;

	cin >> n >> m >> q;
	k = sqrt(n);
	for(int i = 0; i < m; i++) {
		int u, v;
		cin >> u >> v;
		G[v].PB(u);		
	}
	for(int i = 1; i <= n; i++)
		if(!vis[i])
			dfs(i);
	while(q--) {
		int u, y;
		cin >> u >> y;
		vi x(y);
		for(int i = 0; i < y; i++) {
			cin >> x[i];
			no[x[i]] = 1;
		}
		if(y >= k) {
			vi vis(n + 1), dp(n + 1);
			function<int(int)> DP = [&] (int u) {
				if(vis[u]) return dp[u];
				vis[u] = 1;
				if(no[u]) dp[u] = -INF;
				else dp[u] = 0;
 				for(int v:G[u]) {
					dp[u] = max(dp[u], DP(v) + 1);
				}
				return dp[u];
			};
			cout << max(DP(u), -1) << '\n';
		} else {
			int ans = -1;
			for(pi p:who[u]) {
				if(no[p.S] == 0) {
					ans = -p.F;
					break;
				}
			}
			cout << ans << '\n';
		}
		for(int i = 0; i < y; i++) no[x[i]] = 0;
	}

}

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