Submission #979259

#	Time	Username	Problem	Language	Result	Execution time	Memory
979259		Dzadzo	Bitaro’s Party (JOI18_bitaro)	C++17	100 / 100	1838 ms	421388 KiB

bitaro

#include <bits/stdc++.h>
#define ll long long
#define int ll
#define pb push_back
#define S second
#define F first
#define pii pair<int,int>
#define vi vector <int>
#define vvi vector <vi>
#define vvvi vector <vvi>
#define vp vector <pii>
#define vvp vector <vp>
#define vb vector <bool>
#define vvb vector <vb>;
#define INF LLONG_MAX
#define MOD 1000000007
#define MAXN 100000
using namespace std;
vvi adj(MAXN+1);
vvp arr(MAXN+1);
vb seen(MAXN+1);
vi cnt(MAXN+1);
int block;
void dfs(int v){
	seen[v]=true;
	vp cur={{0,v}};
	for (int to:adj[v]){
		if (!seen[to])dfs(to);
		for (auto &[len,u]:arr[to])cur.pb({len+1,u});
	}
	sort(cur.begin(),cur.end());reverse(cur.begin(),cur.end());
	vi k;
	for (int i=0;i<cur.size() && arr[v].size()<block;i++){
		if (!cnt[cur[i].S])arr[v].pb(cur[i]);
		cnt[cur[i].S]++;
		k.pb(cur[i].S);
	}
	for (int x:k)cnt[x]--;
}
vi dp(MAXN+1,-2);
vi del(MAXN+1);
void solve(int v){
	dp[v]=-1;
	if (!del[v])dp[v]=0;
	for (int to:adj[v]){
		if (dp[to]==-2)solve(to);
		if (dp[to]!=-1)dp[v]=max(dp[v],dp[to]+1);
	}
}
signed main(){	
	ios_base::sync_with_stdio(0),cin.tie(NULL),cout.tie(NULL);
	int n,m,q;
	cin>>n>>m>>q;
	for (int i=1;i<=m;i++){
		int u,v;
		cin>>u>>v;
		adj[v].pb(u);
	}
	block=sqrt(n)/2;
	for (int i=1;i<=n;i++){
		if (!seen[i])dfs(i);
	}
	while(q--){
		int t,y;
		cin>>t>>y;
		vi c;
		for (int i=1;i<=y;i++){
			int x;
			cin>>x;
			c.pb(x);
			del[x]++;
		}
		if (y<block){
			bool b=false;
			for (auto &[len,v]:arr[t]){
				if (!del[v]){
					cout<<len<<"\n";
					b=true;
					break;
				}
			}
			if (!b)cout<<-1<<'\n';
		}else{
			dp.assign(n+1,-2);
			solve(t);
			cout<<dp[t]<<'\n';
		}
		for (int x:c)del[x]--;
	}
}

Compilation message (stderr)

bitaro.cpp: In function 'void dfs(long long int)':
bitaro.cpp:33:16: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |  for (int i=0;i<cur.size() && arr[v].size()<block;i++){
      |               ~^~~~~~~~~~~
bitaro.cpp:33:44: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   33 |  for (int i=0;i<cur.size() && arr[v].size()<block;i++){
      |                               ~~~~~~~~~~~~~^~~~~~

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