Submission #322559

#	Time	Username	Problem	Language	Result	Execution time	Memory
322559		NachoLibre	Bitaro’s Party (JOI18_bitaro)	C++14	100 / 100	1815 ms	416572 KiB

bitaro

#include <bits/stdc++.h>
using namespace std;

const int B = 301, N = 100005, M = 200005, Q = N, S = N;
int n, m, q, x, y, c[S], dpn[N];
bool dk[N], gb[N];
vector<int> v[N][2];
vector<pair<int, int> > dp[N];

void G(vector<pair<int, int> > &a, vector<pair<int, int> > b) {
	vector<pair<int, int> > c = a;
	int bp = 0, cp = 0;
	a.clear();
	while((bp < b.size() || cp < c.size()) && a.size() < B) {
		if(bp == b.size()) {
			if(!gb[c[cp].second]) a.push_back(c[cp]);
			gb[c[cp].second] = 1;
			++cp;
		} else if(cp == c.size()) {
			if(!gb[b[bp].second]) a.push_back({b[bp].first + 1, b[bp].second});
			gb[b[bp].second] = 1;
			++bp;
		} else if(b[bp].first + 1 < c[cp].first) {
			if(!gb[c[cp].second]) a.push_back(c[cp]);
			gb[c[cp].second] = 1;
			++cp;
		} else {
			if(!gb[b[bp].second]) a.push_back({b[bp].first + 1, b[bp].second});
			gb[b[bp].second] = 1;
			++bp;
		}
	}
	for(int i = 0; i < a.size(); ++i) {
		gb[a[i].second] = 0;
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> m >> q;
	for(int i = 1; i <= m; ++i) {
		cin >> x >> y;
		v[x][1].push_back(y);
		v[y][0].push_back(x);
	}
	for(int i = 1; i <= n; ++i) {
		dp[i].push_back({0, i});
		for(int j = 0; j < v[i][0].size(); ++j) {
			G(dp[i], dp[v[i][0][j]]);
		}
		// for(int j = 0; j < dp[i].size(); ++j) {
		// 	cout << "[] " << dp[i][j].first << " " << dp[i][j].second << "\n";
		// }
		// cout << "\n";
	}
	for(int qi = 1; qi <= q; ++qi) {
		cin >> x >> y;
		for(int i = 0; i < y; ++i) {
			cin >> c[i];
			dk[c[i]] = 1;
		}
		if(y < B) {
			int ap = -1;
			for(int i = 0; i < dp[x].size(); ++i) {
				if(!dk[dp[x][i].second]) {
					ap = dp[x][i].first;
					break;
				}
			}
			cout << ap << "\n";
		} else {
			for(int i = 1; i <= x; ++i) {
				dpn[i] = 0;
				for(int j = 0; j < v[i][0].size(); ++j) {
					dpn[i] = max(dpn[i], dpn[v[i][0][j]] + 1);
				}
				if(!dpn[i] && dk[i]) dpn[i] = -1;
			}
			cout << dpn[x] << "\n";
		}
		for(int i = 0; i < y; ++i) {
			dk[c[i]] = 0;
		}
	}
	return 0;
}

Compilation message (stderr)

bitaro.cpp: In function 'void G(std::vector<std::pair<int, int> >&, std::vector<std::pair<int, int> >)':
bitaro.cpp:14: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]
   14 |  while((bp < b.size() || cp < c.size()) && a.size() < B) {
      |         ~~~^~~~~~~~~~
bitaro.cpp:14:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   14 |  while((bp < b.size() || cp < c.size()) && a.size() < B) {
      |                          ~~~^~~~~~~~~~
bitaro.cpp:15: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]
   15 |   if(bp == b.size()) {
      |      ~~~^~~~~~~~~~~
bitaro.cpp:19: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]
   19 |   } else if(cp == c.size()) {
      |             ~~~^~~~~~~~~~~
bitaro.cpp:33:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |  for(int i = 0; i < a.size(); ++i) {
      |                 ~~^~~~~~~~~~
bitaro.cpp: In function 'int main()':
bitaro.cpp:49:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |   for(int j = 0; j < v[i][0].size(); ++j) {
      |                  ~~^~~~~~~~~~~~~~~~
bitaro.cpp:65:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |    for(int i = 0; i < dp[x].size(); ++i) {
      |                   ~~^~~~~~~~~~~~~~
bitaro.cpp:75:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |     for(int j = 0; j < v[i][0].size(); ++j) {
      |                    ~~^~~~~~~~~~~~~~~~

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