제출 #517988

#제출 시각아이디문제언어결과실행 시간메모리
517988fatemetmhrBitaro’s Party (JOI18_bitaro)C++17
0 / 100
135 ms27928 KiB
//  ~Be name khoda~  //

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

#define pb       push_back
#define mp       make_pair
#define all(x)   x.begin(), x.end()
#define fi       first
#define se       second
#define cl       clear
#define endll    '\n'

const int maxn  =  1e6   + 10;
const int maxn5 =  2e5   + 10;
const int maxnt =  1.2e6 + 10;
const int maxn3 =  1e3   + 10;
const int mod   =  1e9   +  7;
const int ssq   =  1000;
const ll  inf   =  2e18;

vector <pair<int, int>> mx[maxn5], big, tmp;
int h[maxn5], ans[maxn5];
vector <int> adj[maxn5], jda[maxn5];
vector <int> tp, req[maxn5];
bool mark[maxn5];

inline bool cmp(pair<int, int> a, pair<int, int> b){return a.se > b.se;}

inline void join(int v, int u){
	tmp.clear();
	for(auto p : mx[v])
		tmp.pb(p);
	for(auto p : mx[u])
		tmp.pb({p.fi, p.se + 1});
	sort(all(tmp), cmp);
	while(tmp.size() > ssq + 1)
		tmp.pop_back();
	/*
	int iv = 0, iu = 0;
	while(tmp.size() <= ssq && (iv < mx[v].size() || iu < mx[u].size())){
		if(iv < mx[v].size() && (iu == mx[u].size() || mx[v][iv].se >= mx[u][iu].se + 1)){
			tmp.pb(mx[v][iv]);
			iv++;
		}
		else{
			tmp.pb({mx[u][iu].fi, mx[u][iu].se + 1});
			iu++;
		}
	}
	*/
	mx[v].clear();
	for(auto p : tmp)
		mx[v].pb(p);
	return;
}

inline void dfs(int v){
	mark[v] = true;
	for(auto u : adj[v]) if(!mark[u])
		dfs(u);
	tp.pb(v);
	return;
}

int main()
{
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	
	int n, m, q; cin >> n >> m >> q;
	for(int i = 0; i < m; i++){
		int a, b; cin >> a >> b;
		a--; b--;
		adj[a].pb(b);
		jda[b].pb(a);
	}

	for(int i = 0; i < n; i++) if(!mark[i])
		dfs(i);
	fill(mark, mark + n + 5, false);
	reverse(all(tp));
	for(auto u : tp){
		mx[u].pb({u, 0});
		for(auto v : jda[u]){
			join(u, v);
		}
	}
	memset(ans, -1, sizeof ans);
	
	for(int i = 0; i < q; i++){
		int v, k; cin >> v >> k;
		v--;
		for(int j = 0; j < k; j++){
			int a; cin >> a;
			a--;
			req[i].pb(a);
			if(k < ssq)
				mark[a] = true;
		}
		if(k >= ssq){
			big.pb({i, v});
		}
		else{
			for(auto [u, h] : mx[v]) if(!mark[u]){
				ans[i] = h;
				break;
			}
			for(auto u : req[i])
				mark[u] = false;
		}
	}
	for(auto [id, v] : big){
		memset(h, -1, sizeof h);
		fill(mark, mark + n + 5, false);
		for(auto u : req[id])
			mark[u] = true;
		for(auto u : tp){
			if(!mark[u])
				h[u] = 0;
			for(auto z : jda[u]) if(h[z] > -1)
				h[u] = max(h[u], h[z] + 1);
		}
		ans[id] = h[v];
	}
	for(int i = 0; i < q; i++)
		cout << ans[i] << '\n';
}










#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...