Submission #543228

#	Time	Username	Problem	Language	Result	Execution time	Memory
543228		new_acc	Bitaro’s Party (JOI18_bitaro)	C++14	100 / 100	1020 ms	283220 KiB

bitaro

#include<bits/stdc++.h>
#define fi first
#define se second
#define pitem item*
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
const int sq=350;
const int N=1e5+10;
pair<int,int> t[N][sq];
vi graf[N];
int ile[N],wsk[N],maxi[N];
bitset<N>byl,vis,vis2;
int t2[N];
int n,m,q;
vi tt;
int f(int x){
	vis2[x]=1;
	int ans=-1;
	for(int i=0;i<tt.size();i++){
		int v=tt[i];
		if(!vis2[v]) continue;
		for(auto u:graf[v]) maxi[u]=max(maxi[u],maxi[v]+1),vis2[u]=1;
		if(!byl[v]) ans=max(ans,maxi[v]);
	}
	for(int i=1;i<=n;i++) vis2[i]=0,maxi[i]=0;
	return ans;
}
void solve(){
	cin>>n>>m>>q;
	for(int i=0;i<m;i++){
		int a,b;
		cin>>a>>b;
		graf[b].push_back(a);
		ile[a]++;
	}
	vi curr;
	for(int i=1;i<=n;i++) if(ile[i]==0) curr.push_back(i);
	while(curr.size()){
		int v=curr.back();
		curr.pop_back();
		tt.push_back(v);
		for(auto u:graf[v]){
			ile[u]--;
			if(ile[u]==0) curr.push_back(u);
		}
	}
	int pier=sqrt(n);
	for(int i=tt.size()-1;i>=0;i--){
		int v=tt[i];
		for(auto u:graf[v]) wsk[u]=1;
		for(int j=1;j<=pier;j++){
			int maxi1=0,maxi2=0;	
			for(auto u:graf[v]){
				while(wsk[u]<=pier and (byl[t[u][wsk[u]].fi] or !t[u][wsk[u]].fi)) wsk[u]++;
				if(t[u][wsk[u]].fi!=0 and t[u][wsk[u]].se+1>maxi1) maxi1=t[u][wsk[u]].se+1,maxi2=t[u][wsk[u]].fi; 
			}
			if(maxi1==0){
				t[v][j]={v,0};
				break;
			}
			t[v][j]={maxi2,maxi1};
			byl[maxi2]=1;
		}
		for(int j=1;j<=pier;j++) byl[t[v][j].fi]=0;
	}
	for(int i=1;i<=q;i++){
		int x,il;	
		cin>>x>>il;
		for(int j=1;j<=il;j++){
			int a;
			cin>>a;
			t2[j]=a;
			byl[a]=1;
		}
		if(il<pier){
			int res=-1;
			for(int j=1;j<=pier;j++){
				if(byl[t[x][j].fi] or !t[x][j].fi) continue;
				res=t[x][j].se;
				break;
			}
			cout<<res<<"\n";
		}else cout<<f(x)<<"\n";
		for(int j=1;j<=il;j++) byl[t2[j]]=0;
	}
}
int main(){
	ios_base::sync_with_stdio(0),cin.tie(0);
	solve();
}

Compilation message (stderr)

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

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