Submission #636950

#	Time	Username	Problem	Language	Result	Execution time	Memory
636950		Binaryboy	Bitaro’s Party (JOI18_bitaro)	C++14	100 / 100	1810 ms	258720 KiB

bitaro

#include <bits/stdc++.h>
using namespace std;
const int MAXn = 1e5 + 10, SQ =300 + 10;
typedef pair<int, int> pii;
vector<int> g[MAXn], revg[MAXn];
int n, m, q;
pii dp[MAXn][SQ];
int dp_not_coming[MAXn];
bool in_dp[MAXn];
bool not_coming[MAXn];
inline void makeDp() {
	for (int i = 0; i < n; i++) {
		vector<pii> p_update;
		p_update.push_back(pii(0, i));
		for (int u : revg[i]) {
			vector<pii> to_be_merged;
			int z = 0, j = 0;
			while(z < p_update.size() && (j < SQ && dp[u][j].first != -1)) {
				if (p_update[z].first >= dp[u][j].first + 1)  {
					to_be_merged.push_back(p_update[z]);
					z++;
				}
				else {
					to_be_merged.push_back(pii(dp[u][j].first + 1, dp[u][j].second));
					j++;
				}	
			}
			while(j < SQ && dp[u][j].first != -1) {
				to_be_merged.push_back(pii(dp[u][j].first + 1, dp[u][j].second));
				j++;
			}
			while(z < p_update.size()) {
				to_be_merged.push_back(p_update[z]);
				z++;
			}
		
			p_update.clear();
			for (pii val : to_be_merged)
				if (!in_dp[val.second]) {
					p_update.push_back(val);
					in_dp[val.second] = true;
				}
			for (pii val : p_update) {
				in_dp[val.second] = false;
			}
			if (p_update.size() > SQ)
				p_update.resize(SQ);
		}
		int ind = 0, j = 0;
		while(j < p_update.size() && ind < SQ) {
			dp[i][ind++] = p_update[j];
			j++;
		}
	}
}




inline int get_ans_not_coming(int party_v) {
	for (int i = 0; i <= party_v; i++) {
		if (!not_coming[i]) {
			dp_not_coming[i] = 0;
		}
		else {
			dp_not_coming[i] = -1;
		}
		for (int u : revg[i]) {
			if (dp_not_coming[u] != -1) {
				dp_not_coming[i] = max(dp_not_coming[u] + 1, dp_not_coming[i]);
			}
		}
	}
	return dp_not_coming[party_v];
}


int main() {
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin >> n >> m >> q;
	for (int i = 0; i < m; i++) {
		int u, v;
		cin >> u >> v;u--;v--;
		g[u].push_back(v);
		revg[v].push_back(u);
	}
	for (int i = 0; i < MAXn; i++)
		for (int j = 0; j < SQ; j++)
			dp[i][j] = pii(-1,-1);
	makeDp();
	while(q--) {
		int party_v, cnt_not_coming;
		cin >> party_v >> cnt_not_coming;
		party_v--;
		vector<int> not_coming_query;
		for (int i = 0; i < cnt_not_coming; i++) {
			int v;
			cin >> v;
			v--;
			not_coming_query.push_back(v);
			not_coming[v] = true;
		}
		if (cnt_not_coming < SQ - 1) {
			for (int i = 0; i < SQ; i++)
				if(!not_coming[dp[party_v][i].second]) {
					cout << dp[party_v][i].first << '\n';
					break;
				}
		}
		else {
			cout << get_ans_not_coming(party_v) << '\n';
		}
		
		for (int v : not_coming_query) {
			not_coming[v] = false;
		}
	}
}

Compilation message (stderr)

bitaro.cpp: In function 'void makeDp()':
bitaro.cpp:18:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |    while(z < p_update.size() && (j < SQ && dp[u][j].first != -1)) {
      |          ~~^~~~~~~~~~~~~~~~~
bitaro.cpp:32:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |    while(z < p_update.size()) {
      |          ~~^~~~~~~~~~~~~~~~~
bitaro.cpp:50:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |   while(j < p_update.size() && ind < SQ) {
      |         ~~^~~~~~~~~~~~~~~~~

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