Submission #692217

#	Time	Username	Problem	Language	Result	Execution time	Memory
692217		BJMinhNhut	Bitaro’s Party (JOI18_bitaro)	C++14	100 / 100	1915 ms	414920 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 = 400;
vector<ii> dp[N]; //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);
	}
}

vector<ii> update(vector<ii> &A, vector<ii> &B) {
	vector<ii> ans(0);
	int i = 0, j = 0;
	vi checklist;
	while (ans.size() < SQRT && (i < A.size() || j < B.size())) {
		if (i < A.size() && checked[A[i].second]) ++i;
		else if (j < B.size() && checked[B[j].second]) ++j;
		else if (i == A.size()) {
			ans.pb(mp(B[j].first+1, B[j].second));
			checklist.pb(B[j].second);
			checked[B[j].second] = true;
			++j;
		} else if (j == B.size()) {
			ans.pb(A[i]);
			checklist.pb(A[i].second);
			checked[A[i].second] = true;
			++i;
		} else {
			if (A[i].first > B[j].first+1) {
				ans.pb(A[i]);
				checklist.pb(A[i].second);
				checked[A[i].second] = true;
				++i;
			} else {
				ans.pb(mp(B[j].first+1, B[j].second));
				checklist.pb(B[j].second);
				checked[B[j].second] = true;
				++j;			
			}
		}
	}

	for(int u : checklist) checked[u] = false;
	vi().swap(checklist);
	return ans;
}

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

	// FOR(i, 0, (int)dp[573].size()-1) {
	// 	cout << dp[573][i].first << ' '  << dp[573][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 (best < dp[target].size() && checked[dp[target][best].second]) ++best;
			cout << (best < dp[target].size() ? dp[target][best].first : -1) << '\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 'std::vector<std::pair<int, int> > update(std::vector<std::pair<int, int> >&, std::vector<std::pair<int, int> >&)':
bitaro.cpp:76:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |  while (ans.size() < SQRT && (i < A.size() || j < B.size())) {
      |                               ~~^~~~~~~~~~
bitaro.cpp:76:49: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |  while (ans.size() < SQRT && (i < A.size() || j < B.size())) {
      |                                               ~~^~~~~~~~~~
bitaro.cpp:77:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |   if (i < A.size() && checked[A[i].second]) ++i;
      |       ~~^~~~~~~~~~
bitaro.cpp:78:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |   else if (j < B.size() && checked[B[j].second]) ++j;
      |            ~~^~~~~~~~~~
bitaro.cpp:79:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |   else if (i == A.size()) {
      |            ~~^~~~~~~~~~~
bitaro.cpp:84:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |   } else if (j == B.size()) {
      |              ~~^~~~~~~~~~~
bitaro.cpp: In function 'void Solve()':
bitaro.cpp:130:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  130 |    while (best < dp[target].size() && checked[dp[target][best].second]) ++best;
      |           ~~~~~^~~~~~~~~~~~~~~~~~~
bitaro.cpp:131:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  131 |    cout << (best < dp[target].size() ? dp[target][best].first : -1) << '\n';
      |             ~~~~~^~~~~~~~~~~~~~~~~~~

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