Submission #290526

#	Time	Username	Problem	Language	Result	Execution time	Memory
290526		wwdd	Bitaro’s Party (JOI18_bitaro)	C++14	100 / 100	1665 ms	214396 KiB

bitaro

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> ii;
typedef pair<ii,int> ti;
typedef vector<ii> vii;
typedef vector<int> vi;
typedef vector<vi> vvi;
// whatever
const int SQ = 200;
const int MN = 100010;
vii go[MN];
vvi g;
int dp[MN];
bitset<MN> bs;
int sad(int u, vi& no) {
	for(auto& it: no) {
		bs.set(it);
	}
	for(int i=0;i<go[u].size();i++) {
		int v = go[u][i].second;
		if(!bs[v]) {
			for(auto& it: no) {
				bs.reset(it);
			}
			return go[u][i].first;
		}
	}
	fill(begin(dp),end(dp),-1e9);
	dp[u] = 0;
	int res = -1;
	for(int i=u;i>=0;i--) {
		for(int j=0;j<g[i].size();j++) {
			int v = g[i][j];
			dp[v] = max(dp[v],dp[i]+1);
		}
		if(!bs[i]) {
			res = max(res,dp[i]);
		}
	}
	for(auto& it: no) {
		bs.reset(it);
	}
	return res;
}
int main() {
	ios::sync_with_stdio(0);cin.tie(0);
	int n,m,q;
	cin >> n >> m >> q;
	g.assign(n,vi());
	for(int i=0;i<m;i++) {
		int a,b;
		cin >> a >> b;
		a--;b--;
		g[b].push_back(a);
	}
	for(int i=0;i<n;i++) {
		priority_queue<ti> bo;
		for(int j=0;j<g[i].size();j++) {
			int u = g[i][j];
			bo.push({{go[u].front().first,0},u});
		}
		while(!bo.empty() && go[i].size() < SQ) {
			ti ol = bo.top();bo.pop();
			int u = ol.second;
			ii co = ol.first;
			int idx = co.second;
			ii ens = go[u][idx];
			ens.first++;
			if(!bs[ens.second]) {
				bs.set(ens.second);
				go[i].push_back(ens);
			}
			while(idx < go[u].size() && bs[go[u][idx].second]) {
				idx++;
			}
			if(idx < go[u].size()) {
				bo.push({{go[u][idx].first,idx},u});
			}
		}
		if(go[i].size() < SQ) {
			go[i].push_back({0,i});
		}
		for(auto& it: go[i]) {
			bs.reset(it.second);
		}
	}
	for(int i=0;i<q;i++) {
		int tr,lo;
		cin >> tr >> lo;
		vi no;
		tr--;
		for(int j=0;j<lo;j++) {
			int t;
			cin >> t;
			t--;
			no.push_back(t);
		}
		cout << sad(tr,no) << '\n';
	}
}

Compilation message (stderr)

bitaro.cpp: In function 'int sad(int, vi&)':
bitaro.cpp:20: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]
   20 |  for(int i=0;i<go[u].size();i++) {
      |              ~^~~~~~~~~~~~~
bitaro.cpp:33:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |   for(int j=0;j<g[i].size();j++) {
      |               ~^~~~~~~~~~~~
bitaro.cpp: In function 'int main()':
bitaro.cpp:59:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |   for(int j=0;j<g[i].size();j++) {
      |               ~^~~~~~~~~~~~
bitaro.cpp:74: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]
   74 |    while(idx < go[u].size() && bs[go[u][idx].second]) {
      |          ~~~~^~~~~~~~~~~~~~
bitaro.cpp:77:11: 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(idx < go[u].size()) {
      |       ~~~~^~~~~~~~~~~~~~

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