Submission #984077

#	Time	Username	Problem	Language	Result	Execution time	Memory
984077		Amaarsaa	Bitaro’s Party (JOI18_bitaro)	C++14	14 / 100	983 ms	419092 KiB

bitaro

#include<bits/stdc++.h>
 
using namespace std;
using pii = pair < int, int >;
int used[100001], cant[100001], c[100001], dp[100001];
vector < int > adj[100001], radj[100001];
vector < pii > good[100001];
int main() {
//	freopen("moocast.in", "r", stdin);
//	freopen("moocast.out", "w", stdout);
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n, m, q, i, ans, x, y, I, I1, i1, t;
 
	cin >> n >> m >> q;
	
	for (i = 0; i < m; i ++) {
		cin >> x >> y;
		adj[x].push_back(y);
		radj[y].push_back(x);
	}
	for (i = 1; i <= n; i ++) {
		vector < pii > v;
		for ( int I : radj[i]) {
			i1 = I1 = 0;
			good[I].push_back({0, I});
			while ( v.size() < 350 && (i1 < good[i].size() || I1 < good[I].size())) {
				if (i1 == good[i].size() || (I1 != good[I].size() && good[I][I1].first + 1 >= good[i][i1].first )) {
					good[I][I1].first ++;
					v.push_back(good[I][I1]);
					used[good[I][I1].second] = 1;
					good[I][I1].first --;
					I1 ++;
				}
				else {
					v.push_back(good[i][i1]);
					used[good[i][i1].second] = 1;
					i1 ++;
				}
				while (i1 < good[i].size() && used[good[i][i1].second]) i1 ++;
				while (I1 < good[I].size() && used[good[I][I1].second]) I1 ++;
			}
			good[I].pop_back();
			for ( auto A : v) used[A.second] = 0;
			swap(good[i], v);
		}	
	}
	while ( q --) {
		cin >> t >> m;
		for ( i = 0; i < m; i ++) {
			cin >> c[i];
			cant[c[i]] = 1;
		}
		ans = -1;
		if ( m < 350) {
			for ( auto A : good[t]) {
				if (!cant[A.second]) {
					ans = A.first;
					break;
				}
			}
			if (!cant[t]) ans = max(ans, int(0));
		}
		else {
			for (i = 1; i <= n; i ++) dp[i] = -1;
			dp[t]= 0;
			if (!cant[t]) ans = 0;
			for (i = t - 1; i >= 1; i --) {
				for ( int X : adj[i]) {
					if ( dp[X] != -1) dp[i] = max(dp[i], dp[X] + 1);
				}
				if ( !cant[i]) ans =max(ans, dp[i]);
			}
		}
		for (i =1 ; i <= m; i ++) cant[c[i]] = 0;
		cout << ans << "\n";
	}
}

Compilation message (stderr)

bitaro.cpp: In function 'int main()':
bitaro.cpp:27:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |    while ( v.size() < 350 && (i1 < good[i].size() || I1 < good[I].size())) {
      |                               ~~~^~~~~~~~~~~~~~~~
bitaro.cpp:27:57: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |    while ( v.size() < 350 && (i1 < good[i].size() || I1 < good[I].size())) {
      |                                                      ~~~^~~~~~~~~~~~~~~~
bitaro.cpp:28: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]
   28 |     if (i1 == good[i].size() || (I1 != good[I].size() && good[I][I1].first + 1 >= good[i][i1].first )) {
      |         ~~~^~~~~~~~~~~~~~~~~
bitaro.cpp:28:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |     if (i1 == good[i].size() || (I1 != good[I].size() && good[I][I1].first + 1 >= good[i][i1].first )) {
      |                                  ~~~^~~~~~~~~~~~~~~~~
bitaro.cpp:40:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |     while (i1 < good[i].size() && used[good[i][i1].second]) i1 ++;
      |            ~~~^~~~~~~~~~~~~~~~
bitaro.cpp:41:15: 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 (I1 < good[I].size() && used[good[I][I1].second]) I1 ++;
      |            ~~~^~~~~~~~~~~~~~~~
bitaro.cpp:13:29: warning: unused variable 'I' [-Wunused-variable]
   13 |  int n, m, q, i, ans, x, y, I, I1, i1, t;
      |                             ^

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