Submission #377479

#	Time	Username	Problem	Language	Result	Execution time	Memory
377479		cheissmart	Bitaro’s Party (JOI18_bitaro)	C++14	7 / 100	2080 ms	86716 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];
		for(pi& i:tt) i.F--;
		unordered_map<int, int> mn;
		for(pi p:who[u])
			mn[p.S] = p.F;
		V<pi> ttt, tttt;
		for(pi p:tt) {
			if(mn.count(p.S) && p.F >= mn[p.S])
				continue;
			if(mn.count(p.S) && p.F < mn[p.S]) {
				mn[p.S] = p.F;
			}
			ttt.PB(p);
		}
		for(pi p:who[u]) {
			if(mn[p.S] == p.F) tttt.PB(p);
		}
		V<pi> tmp(ttt.size() + tttt.size());
		merge(ALL(tttt), ALL(ttt), tmp.begin());
		who[u] = tmp;
		if(int(who[u].size()) > k) who[u].resize(k);
	}
}

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--) {
		unordered_set<int> no;
		int u, y;
		cin >> u >> y;
		for(int i = 0; i < y; i++) {
			int x;
			cin >> x;
			no.insert(x);
		}
		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.count(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.count(p.S) == 0) {
					ans = -p.F;
					break;
				}
			}
			cout << ans << '\n';
		}
	}

}

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