Submission #692109

#	Time	Username	Problem	Language	Result	Execution time	Memory
692109		BJMinhNhut	Bitaro’s Party (JOI18_bitaro)	C++14	14 / 100	2050 ms	399668 KiB

bitaro

// Created by BJMinhNhut
#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define FOR(i, a, b) for(int i = (a), _b = (b); i <= _b; ++i) 
#define FORD(i, a, b) for(int i = (a), _b = (b); i >= _b; --i)
#define ALL(a) (a).begin(), (a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define MASK(i) (1ll<<(i))
#define BIT(t, i) (((t)>>(i))&1)
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair<ll, ll> pll;
typedef pair<int, int> ii;

/***Common Functions***/
template <class T>
bool minimize(T &a, T b) {
	if (a > b) {
		a = b;
		return true;
	}
	return false;
}

template <class T>
bool maximize(T &a, T b) {
	if (a < b) {
		a = b;
		return true;
	}
	return false;
}

template<class T>
void read(T &a) {
	a = 0;
	char c; 
	while (!isdigit(c = getchar())) {}
	do {
		a = a*10 + (c-'0');
	} while (isdigit(c = getchar()));
}

template<class T> 
void write(T a){
	if (a > 9) write(a/10);
	putchar(a%10 + '0');
}

/***End of Template***/
int numNodes, numEdges, numQueries;
const int N = 1e5+5;
vi to[N];
const int SQRT = 500;
ii dp[N][SQRT]; //dp[i][j]: j-th longest path to node i
int tmp[N];
bool checked[N];

void Input() {
	cin >> numNodes >> numEdges >> numQueries;
	FOR(i, 1, numEdges) {
		int u, v; cin >> u >> v;
		to[u].pb(v);
	}
}

void update(int cur, int nxt) {
	vector<ii> tmp(0);
	tmp.reserve(SQRT);

	int i = 0, j = 0;
	while (tmp.size() < SQRT) {
		if (i == SQRT) tmp.pb(make_pair(dp[cur][j].first >= 0 ? dp[cur][j].first+1 : dp[cur][j].first, dp[cur][j].second)), ++j;
		else if (j == SQRT) tmp.pb(dp[nxt][i]), ++i;
		else {
			ii nxtdp = dp[nxt][i], curdp = mp(dp[cur][j].first >= 0 ? dp[cur][j].first+1 : dp[cur][j].first, dp[cur][j].second);
			if (curdp < nxtdp) tmp.pb(nxtdp), ++i;
			else if (curdp == nxtdp) tmp.pb(nxtdp), ++i, ++j;
			else tmp.pb(curdp), ++j;
		}
	}

	for(int i = 0; i < SQRT; ++i) dp[nxt][i] = tmp[i];
}

void Solve() {
	memset(dp, -0x3f, sizeof dp);
	FOR(i, 1, numNodes) dp[i][0] = make_pair(0, i);
	FOR(i, 1, numNodes) {
		for(int j : to[i]) update(i, j);
	}

	// FOR(i, 0, numNodes-1) {
	// 	cout << dp[3][i].first << ' '  << dp[3][i].second << '\n';
	// }
	memset(checked, 0, sizeof checked);
	while (numQueries--) {
		int target; cin >> target;
		int absence; cin >> absence;
		if (absence < SQRT) {
			vi abslist(0);
			while (absence--) {
				int u; cin >> u;
				checked[u] = true;
				abslist.pb(u);
			}
			int best = 0;
			while (dp[target][best].second >= 1 && checked[dp[target][best].second]) ++best;
			cout << max(-1, dp[target][best].first) << '\n';

			for(int u : abslist) checked[u] = false;
		} else {
			FOR(i, 1, target) tmp[i] = 0;
			while (absence--) {
				int u; cin >> u;
				tmp[u] = -1e9;
			}
			FOR(i, 1, target) if (tmp[i] >= 0) for(int j : to[i]) maximize(tmp[j], tmp[i] + 1);
			cout << max(-1, tmp[target]) << '\n';
		}
	}
}	

int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	if (fopen("inputf.in", "r")) freopen("inputf.in", "r", stdin);
	Input(), Solve();
	return 0;
}

Compilation message (stderr)

bitaro.cpp: In function 'int main()':
bitaro.cpp:131:38: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  131 |  if (fopen("inputf.in", "r")) freopen("inputf.in", "r", stdin);
      |                               ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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