Submission #69640

#	Time	Username	Problem	Language	Result	Execution time	Memory
69640		yogahmad	Bitaro’s Party (JOI18_bitaro)	C++14	14 / 100	2055 ms	427296 KiB

bitaro

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define fbo find_by_order
#define ook order_of_key
#define f first
#define s second
#define pb push_back
#define reset(a,b) memset(a,b,sizeof a);
#define MOD 1000000007
#define MID (l+r)/2
#define ALL(x) x.begin(),x.end()
#define debug(x) cout<<#x<<" = "<<(x)<<endl
#define mx 100003
#define pc(x) putchar_unlocked(x);
typedef tree<long long, null_type, less<long long>, rb_tree_tag, tree_order_statistics_node_update> pbds;

const int batas=330;
int n,m,q,u,v,t[mx],y[mx],di[mx],dp[mx],ans[mx];
vector<int>ve[mx],isi[mx],b[mx],g[mx];
vector<pair<int,int>>jauh[mx];
bool sudah[mx],ya[mx];
int sem=0;


int main(){
	scanf("%d%d%d",&n,&m,&q);
	for(int i=1;i<=m;i++){
		scanf("%d%d",&u,&v);
		g[u].pb(v);
		b[v].pb(u);
	}
	for(int i=1;i<=q;i++){
		cin>>t[i]>>y[i];
		for(int j=1;j<=y[i];j++){
			int x;
			cin>>x;
			ve[i].pb(x);
		}
		isi[t[i]].pb(i);
	}
	reset(dp,-1);
	for(int i=1;i<=n;i++){
		for(int j:b[i]){
			di[j]=0;
		}
		while(jauh[i].size()<batas+10){
			int ambil=-1,brp=-1;
			for(int j:b[i]){
				while(di[j]<jauh[j].size() && sudah[jauh[j][di[j]].s])di[j]++;
				if(di[j]==jauh[j].size())continue;
				if(brp<jauh[j][di[j]].f){
					brp=jauh[j][di[j]].f;
					ambil=j;
				}
			}
			if(ambil==-1)break;
			int j=ambil;
			jauh[i].pb({brp+1,jauh[j][di[j]].s});
			sudah[jauh[j][di[j]].s]=true;
			di[j]++;
		}
		jauh[i].pb({0,i});
		for(auto x:jauh[i]){
			sudah[x.s]=false;
		}
		for(int x:isi[i]){
			if(y[x]>=batas){
				for(int j:ve[x])ya[j]=true;
				dp[i]=0;
				for(int j=i-1;j>=1;j--){
					for(int k:g[j]){
						if(dp[k]!=-1)dp[j]=max(dp[j],dp[k]+1);
					}
				}
				int aa=-1;
				for(int j=1;j<=i;j++){
					if(!ya[j])aa=max(aa,dp[j]);
				}
				ans[x]=aa;
				for(int j=1;j<=i;j++){
					dp[j]=-1;
				}
				for(int j:ve[x])ya[j]=false;
			}
			else{
				//debug(x);
				for(int j:ve[x])ya[j]=true;
				int aa=-1;
				for(auto j:jauh[i]){
					if(i==2){
					//	cout<<"INI "<<j.f<<" "<<j.s<<endl;
					}
					if(!ya[j.s]){
						aa=j.f;
						break;
					}
				}
				ans[x]=aa;
				for(int j:ve[x])ya[j]=false;
			}
		}
	}
	for(int i=1;i<=q;i++)printf("%d\n",ans[i]);
}

Compilation message (stderr)

bitaro.cpp: In function 'int main()':
bitaro.cpp:52:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while(di[j]<jauh[j].size() && sudah[jauh[j][di[j]].s])di[j]++;
           ~~~~~^~~~~~~~~~~~~~~
bitaro.cpp:53:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(di[j]==jauh[j].size())continue;
        ~~~~~^~~~~~~~~~~~~~~~
bitaro.cpp:29:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d",&n,&m,&q);
  ~~~~~^~~~~~~~~~~~~~~~~~~
bitaro.cpp:31:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d",&u,&v);
   ~~~~~^~~~~~~~~~~~~~

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