제출 #1234245

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1234245		hashdfdfh	Bitaro’s Party (JOI18_bitaro)	C++20	0 / 100	3 ms	7232 KiB

bitaro

#include<bits/stdc++.h>
#define ffor(i,a,b) for(int i=(a);i<=(b);i++)
#define roff(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
const int MAXN=1e5+10,MAXM=400+10;
int n,m,q,len=400,Deg[MAXN],flg[MAXN],deg[MAXN];
vector<int> G[MAXN],g[MAXN]; vector<pair<int,int>> init[MAXN];
vector<pair<int,int>> merge(vector<pair<int,int>> A,vector<pair<int,int>> B) {
	vector<pair<int,int>> ans;
	ffor(i,0,(int)B.size()-1) B[i].first++;
	if(A.empty()) return B;
	if(B.empty()) return A;
	int ida=0,idb=0;
	while(ida<A.size()&&idb<B.size()) {
		if(A[ida]>B[idb]) {
			if(flg[A[ida].second]==0&&ans.size()<len) flg[A[ida].second]=1,ans.push_back(A[ida]);
			ida++;
		}
		else {
			if(flg[B[idb].second]==0&&ans.size()<len) flg[B[idb].second]=1,ans.push_back(B[idb]);
			idb++;
		}
	}
	while(ida<A.size()) {
		if(flg[A[ida].second]==0&&ans.size()<len) flg[A[ida].second]=1,ans.push_back(A[ida]);
		ida++;
	}
	while(idb<B.size()) {
		if(flg[B[idb].second]==0&&ans.size()<len) flg[B[idb].second]=1,ans.push_back(B[idb]);
		idb++;
	}
	for(auto pr:A) flg[pr.second]=0;
	for(auto pr:B) flg[pr.second]=0;
	return ans;
}
int dp[MAXN];
void solve(int u) {
	queue<int> q; int ans=-1;
	ffor(i,1,n) dp[i]=-1,deg[i]=Deg[i];
	dp[u]=0;
	ffor(i,1,n) if(deg[i]==0) q.push(i);
	while(!q.empty()) {
		int u=q.front(); q.pop();
		for(auto v:g[u]) {
			deg[v]--; if(deg[v]==0) q.push(v);
			if(dp[u]>=0) dp[v]=max(dp[v],dp[u]+1);
		}
	}
	ffor(i,1,n) ans=max(ans,dp[i]);
	cout<<ans<<'\n';
	return ;
}
int main() {
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>n>>m>>q;
	ffor(i,1,m) {int u,v; cin>>u>>v,G[u].push_back(v),g[v].push_back(u),deg[v]++,Deg[u]++;}
	queue<int> que; ffor(i,1,n) if(deg[i]==0) que.push(i);
	while(!que.empty()) {
		int u=que.front(); que.pop();
		if(init[u].size()<len) init[u].push_back({0,u});
		for(auto v:G[u]) {
			deg[v]--,merge(init[v],init[u]);
			if(deg[v]==0) que.push(v);
		}
	}
	ffor(i,1,q) {
		int u,cnt; cin>>u>>cnt;
		vector<int> id;
		ffor(j,1,cnt) {int v; cin>>v,id.push_back(v),flg[v]=1;}
		if(cnt<=len) {
			int ans=-1;
			for(auto pr:init[u]) if(flg[pr.second]==0&&pr.second!=u) {ans=pr.first;break;}	
			cout<<ans<<'\n';
		}
		else solve(u);
		for(auto v:id) flg[v]=0;
	}
	return 0;
}

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