Submission #100688

#	Time	Username	Problem	Language	Result	Execution time	Memory
100688		JPN20	Bitaro’s Party (JOI18_bitaro)	C++17	14 / 100	2063 ms	79848 KiB

bitaro

#include <bits/stdc++.h>
using namespace std;

const int BACKET = 50;
int N, M, Q, A[1 << 18], B[1 << 18], dp[1 << 18];
vector<int>X[1 << 18], Y[1 << 18];
vector<pair<int, int>> G[1 << 18];
bool used[1 << 18];

int melee_solve(int pos, vector<int>vec) {
	for (int i = 0; i < (int)vec.size(); i++) used[vec[i]] = true;
	
	int maxn = -1;
	for (int i = 0; i < (int)G[pos].size(); i++) {
		if (used[G[pos][i].second] == false) maxn = max(maxn, G[pos][i].first);
	}
	for (int i = 0; i < (int)vec.size(); i++) used[vec[i]] = false;
	return maxn;
}
int ranged_solve(int pos, vector<int>vec) {
	for (int i = 1; i <= N; i++) dp[i] = -1;
	for (int i = 0; i < (int)vec.size(); i++) used[vec[i]] = true;
	
	for (int i = 1; i <= N; i++) {
		if (used[i] == false) dp[i] = 0;
		for (int j = 0; j < (int)Y[i].size(); j++) {
			if (dp[Y[i][j]] == -1) continue;
			dp[i] = max(dp[i], dp[Y[i][j]] + 1);
		}
	}
	for (int i = 0; i < (int)vec.size(); i++) used[vec[i]] = false;
	return dp[pos];
}

void init() {
	for (int i = 1; i <= N; i++) {
		vector<pair<int, int>>Z;
		for (int j = 0; j < (int)Y[i].size(); j++) {
			for (int k = 0; k < (int)G[Y[i][j]].size(); k++) {
				Z.push_back(make_pair(G[Y[i][j]][k].first + 1, G[Y[i][j]][k].second));
			}
		}
		Z.push_back(make_pair(0, i));
		sort(Z.begin(), Z.end(), greater<pair<int, int>>());
		
		for (int j = 0; j < (int)Z.size(); j++) {
			if (used[Z[j].second] == false) { used[Z[j].second] = true; G[i].push_back(Z[j]); }
			if (G[i].size() >= BACKET) break;
		}
		
		for (int j = 0; j < (int)Z.size(); j++) used[Z[j].second] = false;
	}
}

int main(){
	scanf("%d%d%d", &N, &M, &Q);
	for (int i = 0; i < M; i++) {
		scanf("%d%d", &A[i], &B[i]);
		X[A[i]].push_back(B[i]);
		Y[B[i]].push_back(A[i]);
	}
	
	init();
	
	for (int i = 1; i <= Q; i++) {
		int P, S, C; vector<int>vec1;
		scanf("%d%d", &P, &S);
		for (int j = 0; j < S; j++) {
			scanf("%d", &C); vec1.push_back(C);
		}
		
		int ans = 0;
		if (S < BACKET) ans = melee_solve(P, vec1);
		else ans = ranged_solve(P, vec1);
		
		printf("%d\n", ans);
	}
	return 0;
}

Compilation message (stderr)

bitaro.cpp: In function 'int main()':
bitaro.cpp:56:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d", &N, &M, &Q);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
bitaro.cpp:58:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &A[i], &B[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~
bitaro.cpp:67:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &P, &S);
   ~~~~~^~~~~~~~~~~~~~~~
bitaro.cpp:69:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d", &C); vec1.push_back(C);
    ~~~~~^~~~~~~~~~

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