Submission #457712

#	Time	Username	Problem	Language	Result	Execution time	Memory
457712		zeyu	Bitaro’s Party (JOI18_bitaro)	C++17	0 / 100	53 ms	17100 KiB

bitaro

#include <bits/stdc++.h>
#define maxn 100010
using namespace std;
const int B = 320;
int n, m, q;
typedef pair<int, int> pi;
vector<int> prv[maxn];
set<pi> top[maxn];
set<pi> pot[maxn];

void add(pi p, int i){
	set<pi>::iterator q = pot[i].lower_bound(make_pair(p.second, 0));
	if (q != pot[i].end() && q -> first == p.second){
		p = max(p, make_pair(q -> second, q -> first));
		pot[i].erase(q);
		pot[i].insert(make_pair(p.second, p.first));
		top[i].erase(make_pair(q -> second, q -> first));
		top[i].insert(p);
	} else{
		if (top[i].size() < B){
			top[i].insert(p);
			pot[i].insert(make_pair(p.second, p.first));
		} else{
			if (top[i].begin() -> first < p.first){
				top[i].erase(top[i].begin());
				top[i].insert(p);
				pot[i].insert(make_pair(p.second, p.first));
			}
		}
	}
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> m >> q;
	for (int i = 0; i < m; i ++){
		int x, y;
		cin >> x >> y;
		x --; y --;
		prv[y].push_back(x);
	}
	for (int i = 0; i < n; i ++){
		top[i].insert(make_pair(0, i));
		pot[i].insert(make_pair(i, 0));
	}
	for (int i = 0; i < n; i ++){
		for (int j = 0; j < prv[i].size(); j ++){
			int x = prv[i][j];
			for (set<pi>::iterator it = top[x].begin(); it != top[x].end(); it ++){
				add(make_pair(it -> first + 1, it -> second), i);
			}
			add(make_pair(1, x), i);
		}
	}
	while(q --){
		int t; cin >> t; t --;
		int r; cin >> r;
		set<int> y;
		for (int i = 0; i < r; i ++){
			int p; cin >> p; p --;
			y.insert(p);
		}
		if (r >= B){
			vector<int> dp(n, -1);
			for (int i = 0; i < n; i ++){
				if (y.find(i) == y.end()){
					dp[i] = max(dp[i], 0);
				}
				for (int j = 0; j < prv[i].size(); j ++){
					dp[i] = max(dp[i], dp[prv[i][j]] + 1);
				}
			}
			cout << dp[t] << '\n';
		} else{
			for (set<pi>::reverse_iterator it = top[t].rbegin(); it != top[t].rend(); it ++){
				if (y.find(it -> second) == y.end()){
					cout << it -> first << '\n';
					goto done;
				}
			}
			cout << -1 << '\n';
			done: continue;
		}
	}
}

Compilation message (stderr)

bitaro.cpp: In function 'int main()':
bitaro.cpp:48:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |   for (int j = 0; j < prv[i].size(); j ++){
      |                   ~~^~~~~~~~~~~~~~~
bitaro.cpp:70:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |     for (int j = 0; j < prv[i].size(); j ++){
      |                     ~~^~~~~~~~~~~~~~~

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