Submission #636947

#	Time	Username	Problem	Language	Result	Execution time	Memory
636947		Binaryboy	Bitaro’s Party (JOI18_bitaro)	C++14	14 / 100	780 ms	255244 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];
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) {
					to_be_merged.push_back(p_update[z]);
					z++;
				}
				else {
					to_be_merged.push_back(dp[u][j]);
					j++;
				}	
			}
			while(j < SQ && dp[u][j].first != -1) {
				to_be_merged.push_back(dp[u][j]);
				j++;
			}
			while(z < p_update.size()) {
				to_be_merged.push_back(p_update[z]);
				z++;
			}
			if (to_be_merged.size() > SQ)
				to_be_merged.resize(SQ);
			p_update = to_be_merged;
		}
		int ind = 0, j = 0;
		while(j < p_update.size() && ind < SQ) {
			if (!in_dp[p_update[j].second]) {
				in_dp[p_update[j].second] = true;
				dp[i][ind++] = pii(p_update[j]);
			}
			j++;
		}
		for (int x = 0; x < ind; x++) {
			in_dp[dp[i][x].second] = false;
		}
	}
}




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:41: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]
   41 |   while(j < p_update.size() && ind < SQ) {
      |         ~~^~~~~~~~~~~~~~~~~

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