oj.uz

Submission #94253

# Submission time Handle Problem Language Result Execution time Memory
94253 2019-01-17T06:55:24 Z autumn_eel Bitaro’s Party (JOI18_bitaro) C++14
0 / 100
 23 ms 23864 KB 
#include <bits/stdc++.h>
#define rep(i,n)for(int i=0;i<(n);i++)
#define INF 0x3f3f3f3f
using namespace std;
typedef pair<int,int>P;

#define B 200

vector<int>E[200000];
set<P>dp[200000];
map<int,int>mp[200000];

int dp2[200000];

int main(){
	int n,m,q;cin>>n>>m>>q;
	rep(i,m){
		int s,t;scanf("%d%d",&s,&t);s--;t--;
		E[s].push_back(t);
	}
	rep(i,n)dp[i].insert(P(0,i));
	rep(i,n){
		for(auto p:dp[i]){
			for(int u:E[i]){
				if(mp[u][p.second]<=p.first){
					dp[u].erase(P(mp[u][p.second],p.second));
					mp[u][p.second]=p.first+1;
					dp[u].insert(P(mp[u][p.second],p.second));
				}
				while(dp[u].size()>B)dp[u].erase(dp[u].begin());//上位B個だけを保持
			}
		}
	}
	rep(i,q){
		int t,y;scanf("%d%d",&t,&y);t--;
		set<int>v;
		rep(j,y){
			int c;scanf("%d",&c);c--;
			v.insert(c);
		}
		if(y<B){
			int Max=0;
			for(auto p:dp[t]){
				if(!v.count(p.second)){
					Max=max(Max,p.first);
				}
			}
			printf("%d\n",Max);
		}
		else{
			rep(i,n){
				if(!v.count(i))dp2[i]=0;
				else dp2[i]=-INF;
			}
			rep(i,n){
				for(int u:E[i]){
					dp2[u]=max(dp2[u],dp2[i]+1);
				}
			}
			printf("%d\n",dp2[t]==-INF?-1:dp2[t]);
		}
	}
}

Compilation message

bitaro.cpp: In function 'int main()':
bitaro.cpp:18:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int s,t;scanf("%d%d",&s,&t);s--;t--;
           ~~~~~^~~~~~~~~~~~~~
bitaro.cpp:35:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int t,y;scanf("%d%d",&t,&y);t--;
           ~~~~~^~~~~~~~~~~~~~
bitaro.cpp:38:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    int c;scanf("%d",&c);c--;
          ~~~~~^~~~~~~~~

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 23800 KB Output is correct
2 Incorrect 23 ms 23864 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 23800 KB Output is correct
2 Incorrect 23 ms 23864 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 86.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 23800 KB Output is correct
2 Incorrect 23 ms 23864 KB Output isn't correct
3 Halted 0 ms 0 KB -