Submission #1030136

#	Time	Username	Problem	Language	Result	Execution time	Memory
1030136		SamuellH12	Bitaro’s Party (JOI18_bitaro)	C++17	7 / 100	1701 ms	524288 KiB

bitaro

#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 = 316;
using namespace std;

int block[MAXN], tempo = 0;
vi trafo[MAXN];
set<pii> best[MAXN];

vi order;
int deg[MAXN];
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

void get_order(int n){
	queue<int> fila;

	for(int i=1; i<=n; i++)	
		if(deg[i] == 0)
			fila.emplace(i);

	while(!fila.empty())
	{
		auto u = fila.front();
		fila.pop();
		order.emplace_back(u);

		for(auto v : trafo[u])
			if(--deg[v] == 0)
				fila.emplace(v);

		shuffle(ALL(trafo[u]), rng);
	}

	reverse(ALL(order));
}

void precalc(){
	for(auto u : order)
	{
		for(auto v : trafo[u])
		{
			for(auto [x, w] : best[v])
			{
				if(best[u].size() >= SQRT && (x-1) > best[u].rbegin()->first) break;
				
				best[u].emplace(x-1, w);
			
				if(best[u].size() > SQRT) 
					best[u].erase(--(best[u].end()));
			}
			
			best[u].emplace(-1, v);
		}

		while(best[u].size() > SQRT) 
			best[u].erase(--(best[u].end()));
	}
}

int dp[MAXN];
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) break;
	}

	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);
		deg[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;

		for(auto [x, w] : best[t]) 
			if(block[w] != tempo)
			{
				ans = -x;
				break;
			}

		if(ans == -1) ans = solve(t);
		
		cout << ans << endl;
	}

	return 0;	
}

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