oj.uz

답안 #94284

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
94284 2019-01-17T10:00:53 Z autumn_eel Bitaro’s Party (JOI18_bitaro) C++14
0 / 100
 16 ms 10116 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 40

vector<int>E[200000];
vector<P>dp[200000];

int dp2[200000];
bool b[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[t].push_back(s);
	}
	rep(i,n)dp[i].push_back(P(0,i));
	rep(i,n){
		map<int,int>mp;
		for(int u:E[i]){
			for(auto&p:dp[u])mp[p.second]=max(mp[p.second],p.first+1);
		}
		for(auto&p:mp){
			dp[i].push_back(P(p.second,p.first));
		}
		sort(dp[i].begin(),dp[i].end(),greater<>());
		while(dp[i].size()>B)dp[i].pop_back();
	}
	rep(i,q){
		int t,y;scanf("%d%d",&t,&y);t--;
		vector<int>v;
		rep(j,y){
			int c;scanf("%d",&c);c--;
			v.push_back(c);
		}
		if(y<B){
			for(int i:v)b[i]=true;
			for(auto&p:dp[t]){
				if(!b[p.second]){
					printf("%d\n",p.first);
					goto g;
				}
			}
			puts("-1");
			g:;
			for(int i:v)b[i]=false;
		}
		else{
			fill(dp2,dp2+n,0);
			for(int i:v)dp2[i]=-INF;
			rep(i,n){
				for(int u:E[i]){
					dp2[u]=max(dp2[u],dp2[i]+1);
				}
			}
			printf("%d\n",dp2[t]<0?-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:34: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:37: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

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 9720 KB Output is correct
2 Correct 8 ms 9720 KB Output is correct
3 Correct 10 ms 9764 KB Output is correct
4 Correct 8 ms 9720 KB Output is correct
5 Incorrect 16 ms 10116 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 9720 KB Output is correct
2 Correct 8 ms 9720 KB Output is correct
3 Correct 10 ms 9764 KB Output is correct
4 Correct 8 ms 9720 KB Output is correct
5 Incorrect 16 ms 10116 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 86.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 9720 KB Output is correct
2 Correct 8 ms 9720 KB Output is correct
3 Correct 10 ms 9764 KB Output is correct
4 Correct 8 ms 9720 KB Output is correct
5 Incorrect 16 ms 10116 KB Output isn't correct
6 Halted 0 ms 0 KB -