Submission #100695

#	Time	Username	Problem	Language	Result	Execution time	Memory
100695		JPN20	Bitaro’s Party (JOI18_bitaro)	C++17	100 / 100	1385 ms	119652 KiB

bitaro

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

const int BACKET = 60;
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>> vec1;

pair<int, int> G[1 << 17][120], I[12000000]; int SZ[1 << 17];
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 < SZ[pos]; i++) {
		if (used[G[pos][i].second] == false) { maxn = max(maxn, G[pos][i].first); break; }
	}
	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] = 0;
	for (int i = 0; i < (int)vec.size(); i++) dp[vec[i]] = -1000000;
	
	for (int i = 0; i < M; i++) {
		dp[B[i]] = max(dp[B[i]], dp[A[i]] + 1);
	}
	return max(-1, dp[pos]);
}

void init() {
	for (int i = 1; i <= N; i++) {
		int cntv = 0, cnts = 0;
		for (int pos : Y[i]) {
			for (int k = 0; k < SZ[pos]; k++) {
				I[cntv] = make_pair(G[pos][k].first + 1, G[pos][k].second); cntv++;
			}
		}
		I[cntv] = make_pair(0, i); cntv++;
		sort(I, I + cntv, greater<pair<int, int>>());
		
		for (int j = 0; j < cntv; j++) {
			if (used[I[j].second] == false) { used[I[j].second] = true; G[i][cnts] = I[j]; cnts++; }
			if (cnts >= BACKET) break;
		}
		SZ[i] = cnts;
		
		for (int j = 0; j < cntv; j++) used[I[j].second] = false;
	}
}

int main(){
	//FILE *in = freopen("in1.txt", "r", stdin);
	//FILE *out = freopen("out1.txt", "w", stdout);
	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]);
		vec1.push_back(make_pair(A[i], B[i]));
	}
	sort(vec1.begin(), vec1.end());
	for (int i = 0; i < M; i++) {
		A[i] = vec1[i].first;
		B[i] = vec1[i].second;
	}
	
	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:58: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:60: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:75: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:77: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: 86 / 86