Submission #1087933

#	Time	Username	Problem	Language	Result	Execution time	Memory
1087933		4QT0R	Bitaro’s Party (JOI18_bitaro)	C++17	14 / 100	2044 ms	17360 KiB

bitaro

#include <bits/stdc++.h>
using namespace std;
#define pii pair<int,int>

vector<pii> best[100003];
vector<int> graph[100003];
vector<int> rev[100003];
bool toff[100003];
int vis[100003];
int dp[100003];

const int siz=300;

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	int n,m,q;
	cin >> n >> m >> q;
	for (int i = 1,s,t; i<=m; i++){
		cin >> s >> t;
		graph[s].push_back(t);
		rev[t].push_back(s);
	}
	// priority_queue<pii> pq;
	// for (int i = 1; i<=n; i++){
	// 	pq.push({0,i});
	// 	for (auto u : rev[i]){
	// 		for (auto [v,d] : best[u]){
	// 			pq.push({d+1,v});
	// 		}
	// 	}
	// 	for (;best[i].size()<siz && pq.size();pq.pop()){
	// 		auto [d,v] = pq.top();
	// 		if (vis[v]!=i){
	// 			vis[v]=i;
	// 			best[i].push_back({v,d});
	// 		}
	// 	}
	// 	for(;pq.size();pq.pop());
	// }
	vector<int> wej;
	for (int i = 1, fin, num; i<=q; i++){
		cin >> fin >> num;
		for (int j = 1, v; j<=num; j++){
			cin >> v;
			wej.push_back(v);
		}
		for (auto u : wej)toff[u]=true;
		// if (num>=siz){
		if (true){
			fill(dp,dp+fin+1,-1);
			dp[fin]=0;
			for (int i = fin; i>0; i--){
				if (dp[i]==-1)continue;
				for (auto u : rev[i]){
					dp[u]=max(dp[i]+1,dp[u]);
				}
			}
			int ans=-1;
			for (int i = 1; i<=fin; i++)if (!toff[i])ans=max(ans,dp[i]);
			cout << ans << '\n';
		}
		// else{
		// 	int ans=-1;
		// 	for (auto [u,d] : best[fin]){
		// 		if (!toff[u])ans=max(ans,d);
		// 	}
		// 	cout << ans << '\n';
		// }
		for (auto u : wej)toff[u]=false;
		wej.clear();
	}
}

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