Submission #370605

#	Time	Username	Problem	Language	Result	Execution time	Memory
370605		nafis_shifat	Bitaro’s Party (JOI18_bitaro)	C++14	100 / 100	1455 ms	415084 KiB

bitaro

#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
using namespace std;
const int mxn=1e5 +5;
const int inf=1e9;
const int B = 320;
int n,m,q;
vector<int> adj[mxn];
vector<pii> city[mxn];
int vis[mxn] = {};
int main() {
	cin >> n >> m >> q;
	for(int i = 1; i <= m; i++) {
		int u,v;
		scanf("%d%d",&u, &v);
		adj[v].push_back(u);
	}

	for(int i = 1; i <= n; i++) {
		city[i].push_back({0,i});
		vis[i] = 1;
		int ind = 1;
		for(int j : adj[i]) {
			for(pii k : city[j]) {
				int u = k.second;
				int dist = k.first + 1;
				if(vis[u]) {
					city[i][vis[u] - 1] = max(city[i][vis[u] - 1],{dist,u});
				} else {
					ind++;
					city[i].push_back({dist,u});
					vis[u] = ind;
				}
			}
		}
		nth_element(city[i].begin(),city[i].begin() + B,city[i].end(),greater<pii>());
		for(pii j : city[i]) vis[j.second] = 0;
		while(city[i].size() > B) city[i].pop_back();
	}
	
	


	int blocked[n + 1] = {};
	while(q--) {
		int d,k;
		scanf("%d%d",&d,&k);
		vector<int> C;
		for(int i = 1; i <= k; i++) {
			int x;
			scanf("%d",&x);
			C.push_back(x);
			blocked[x] = 1;
		}

		if(k >= B) {
			int dp[d+1];
			for(int i = 1; i <= d; i++) dp[i] = -inf;
			dp[d] = 0;

		    for(int i = d; i >= 1; i--) {
		    	for(int j : adj[i]) {
		    		if(dp[j] < dp[i] + 1) dp[j] = dp[i] + 1;
		    	}
		    }

		    int ans = -1;
		    for(int i = 1; i <= d; i++) {
		    	if(blocked[i]) continue;
		    	ans = max(ans,dp[i]);
		    }

		    printf("%d\n",ans);
		} else {
			int ans = -1;
			for(pii i : city[d]) {
				int u = i.second;
				if(blocked[u]) continue;
				ans = max(ans,i.first);
			}

			printf("%d\n",ans);
		}


		for(int i : C) blocked[i] = 0;
	}
	


}

Compilation message (stderr)

bitaro.cpp: In function 'int main()':
bitaro.cpp:16:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   16 |   scanf("%d%d",&u, &v);
      |   ~~~~~^~~~~~~~~~~~~~~
bitaro.cpp:48:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   48 |   scanf("%d%d",&d,&k);
      |   ~~~~~^~~~~~~~~~~~~~
bitaro.cpp:52:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   52 |    scanf("%d",&x);
      |    ~~~~~^~~~~~~~~

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