Submission #1030097

#	Time	Username	Problem	Language	Result	Execution time	Memory
1030097		SamuellH12	Bitaro’s Party (JOI18_bitaro)	C++17	14 / 100	2095 ms	15700 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 ll long long
#define vi vector<int>
#define pii pair<int,int>
#define INF 0x3f3f3f3f
const int MAXN = 1e5 + 5;
const int SQRT = 700;
using namespace std;

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

void precalc(int u){
	for(auto v : trafo[u])
	{
		precalc(v);
		for(auto [x, w] : best[v]) best[u].emplace_back(x+1, w);
		best[u].emplace_back(1, v);
	}

	sort(best[u].rbegin(), best[u].rend());
	while(best[u].size() > SQRT) best[u].pop_back();
}

int dp[MAXN];
int calc[MAXN], iter = 0;

int solve(int u){
	if(calc[u] == iter) return dp[u];
	int ans = (block[u] == tempo ? -1 : 0);

	for(auto v : trafo[u])
	{
		int temp = solve(v)+1;
		if(temp) ans = max(ans, temp);
	}

	calc[u] = iter;
	return dp[u] = ans;
}

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);
	}

	//for(int i=1; i<=n; i++)
	//	precalc(i);

	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) iter++, ans = solve(t);
		
		cout << ans << endl;
	}

	return 0;	
}

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