Submission #1030175

#TimeUsernameProblemLanguageResultExecution timeMemory
1030175SamuellH12Bitaro’s Party (JOI18_bitaro)C++17
14 / 100
2035 ms469812 KiB
#include <bits/stdc++.h>
#define optimize ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
#define ALL(x) x.begin(), x.end()
#define endl "\n"
#define vi vector<int>
#define pii pair<int,int>
const int MAXN = 1e5 + 5;
const int SQRT = 200;
using namespace std;
 
int block[MAXN], dp[MAXN], tempo;
vi trafo[MAXN], order;
vector<pii> best[MAXN];

void get_order(int n){
	queue<int> fila;
 
	for(int i=1; i<=n; i++)	
		if(dp[i] == 0)
			fila.emplace(i);
 
	while(!fila.empty())
	{
		auto u = fila.front(); fila.pop();
		order.emplace_back(u);
 
		for(auto v : trafo[u])
			if(--dp[v] == 0)
				fila.emplace(v);
	}
 
	reverse(ALL(order));
}
 
void precalc(){
	for(auto u : order)
	{
        best[u].emplace_back(0, u);
		for(auto v : trafo[u])
			for(auto [x, w] : best[v])
				if(best[u].back() != pii(x-1, w))
					best[u].emplace_back(x-1, w);
 
		sort(ALL(best[u]));
		best[u].resize(min(SQRT, (int)(unique(ALL(best[u])) - best[u].begin())));
		// if(best[u].size() > SQRT) best[u].resize(SQRT);
	}
}
 
int solve(int w){
	for(auto u : order)
	{
		dp[u] = (block[u] == tempo ? -1 : 0);
 
		for(auto v : trafo[u])
			if(~dp[v]) 
				dp[u] = max(dp[u], dp[v]+1);
 
		if(u == w) return dp[u];
	}
	
	assert(false);
	return dp[w];
}
 
int main(){
	optimize;
	int n, m, q;
	cin >> n >> m >> q;
	
	for(int i=0, u, v; i<m; i++)
	{
		cin >> u >> v;
		trafo[v].emplace_back(u);
		dp[u]++;
	}
 
	get_order(n);
	precalc();
 
	int t, y;
	while(q--)
	{
		tempo++;
		cin >> t >> y;
 
		for(int i=0, x; i<y; i++)
			cin >> x, block[x] = tempo;
 
		int ans = -1;
		bool ok = false;
 
		for(auto [x, w] : best[t]) 
			if(block[w] != tempo)
			{
				ans = -x;
				ok = true;
				break;
			}
 
		if(!ok) ans = solve(t);
		
		cout << ans << endl;
	}
 
	return 0;	
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...