Submission #218638

#	Time	Username	Problem	Language	Result	Execution time	Memory
218638		someone_aa	Bitaro’s Party (JOI18_bitaro)	C++17	14 / 100	1620 ms	228460 KiB

bitaro

#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair
#define vpii vector<pair<int,int> > 
using namespace std;
const int maxn = 100100;
const int block = 200;

vector<pair<int,int> > v[maxn];
vector<int>ig[maxn], g[maxn];
vector<int>order;

int n, m, q;

bool blocked[maxn];
bool visited[maxn];
int dp[maxn];

void dfs(int node) {
	if(visited[node]) return;
	visited[node] = true;

	for(int i:ig[node]) {
		if(!visited[i]) {
			dfs(i);
		}
	}
	order.pb(node);
}

int brute_force(int node) {
	dfs(node);
	reverse(order.begin(), order.end());

	int result = -1;
	for(int i=0;i<order.size();i++) {
		int node=order[i];

		for(int i:g[node]) {
			if(!visited[i]) continue;

			dp[node] = max(dp[node], dp[i] + 1);
		}

		//cout<<node<<": "<<dp[node]<<"\n";

		if(!blocked[node])
			result = max(result, dp[node]);
	}

	memset(dp, 0, sizeof(dp));
	memset(visited,false,sizeof(visited));
	order.clear();

	return result;
}

bool used_node[maxn];
vpii merge_vector(vpii a, vpii b) {
	vpii nw;

	/*cout<<"Merging \n";
	for(auto i:a) cout<<i.first<<" at "<<i.second<<"\n";
	cout<<"With \n";
	for(auto i:b) cout<<i.first<<" at "<<i.second<<"\n";*/

	int pb = 0;
	for(auto i:a) {
		//cout<<i.first<<" at node "<<i.second<<"\n";
		while(pb < b.size() && b[pb].first + 1 > i.first) {
			if(used_node[b[pb].second]) {
				pb++;
				continue;
			}
			else {
				used_node[b[pb].second] = true;
				nw.pb(mp(b[pb].first +1, b[pb].second));
			}
			pb++;
		}

		//cout<<"Here: "<<pb<<"\n";

		if(used_node[i.second]) continue;
		used_node[i.second] = true;
		nw.pb(i);
	}

	while(pb < b.size()) {
		if(!used_node[b[pb].second]) {
			used_node[b[pb].second] = true;
			nw.pb(mp(b[pb].first +1, b[pb].second));
		}
		pb++;
	}

	for(auto i:nw) used_node[i.second] = false;
	while(nw.size() > block) {
		nw.pop_back();
	}

	return nw;
}

void preprocess() {
	for(int node=1;node<=n;node++) {
		v[node].pb(mp(0, node));
		for(int i:ig[node]) {
			//cout<<"Starting merging "<<node<<" with "<<i<<"\n";
			v[node] = merge_vector(v[node], v[i]);
			/*cout<<"Done merging: \n";
			for(auto i:v[node]) {
				cout<<i.first<<" "<<i.second<<"\n";
			}*/
		}
		/*cout<<"Finish "<<node<<": \n";
		for(auto i:v[node]) {
			cout<<i.first<<" "<<i.second<<"\n";
		}*/
	}
}


void solve() {
 	int node, qs, x;
	vector<int>points;
	cin>>node>>qs;
	for(int i=0;i<qs;i++) {
		cin>>x;
		points.pb(x);
		blocked[x] = true;
	}

	if(qs >= block) {
		cout<<brute_force(node);
		for(int i:points) blocked[i] = false;
		return;
	}

	int maxtunnels = -1;
	for(auto i:v[node]) {
		if(!blocked[i.second]) maxtunnels = max(maxtunnels, i.first);
	}
	cout<<maxtunnels<<"\n";

	for(int i:points) blocked[i] = false;
}

int main() {
	cin>>n>>m>>q;

	int a, b;
	for(int i=0;i<m;i++) {
		cin>>a>>b;
		g[a].pb(b);
		ig[b].pb(a);
	}

	preprocess();
	while(q--) {
		solve();
	}
}

Compilation message (stderr)

bitaro.cpp: In function 'int brute_force(int)':
bitaro.cpp:37:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<order.size();i++) {
              ~^~~~~~~~~~~~~
bitaro.cpp: In function 'std::vector<std::pair<int, int> > merge_vector(std::vector<std::pair<int, int> >, std::vector<std::pair<int, int> >)':
bitaro.cpp:71:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(pb < b.size() && b[pb].first + 1 > i.first) {
            ^
bitaro.cpp:90:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while(pb < b.size()) {
           ^

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