oj.uz

답안 #94254

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
94254 2019-01-17T06:56:31 Z autumn_eel Bitaro’s Party (JOI18_bitaro) C++14
0 / 100
 157 ms 40912 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=-1;
			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

# 결과 실행 시간 메모리 Grader output
1 Correct 20 ms 23772 KB Output is correct
2 Correct 19 ms 23800 KB Output is correct
3 Correct 19 ms 23800 KB Output is correct
4 Correct 22 ms 23800 KB Output is correct
5 Correct 39 ms 27384 KB Output is correct
6 Correct 39 ms 27512 KB Output is correct
7 Correct 38 ms 27128 KB Output is correct
8 Correct 138 ms 40756 KB Output is correct
9 Correct 144 ms 40912 KB Output is correct
10 Correct 145 ms 40792 KB Output is correct
11 Correct 148 ms 39416 KB Output is correct
12 Correct 92 ms 33324 KB Output is correct
13 Incorrect 157 ms 39104 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 20 ms 23772 KB Output is correct
2 Correct 19 ms 23800 KB Output is correct
3 Correct 19 ms 23800 KB Output is correct
4 Correct 22 ms 23800 KB Output is correct
5 Correct 39 ms 27384 KB Output is correct
6 Correct 39 ms 27512 KB Output is correct
7 Correct 38 ms 27128 KB Output is correct
8 Correct 138 ms 40756 KB Output is correct
9 Correct 144 ms 40912 KB Output is correct
10 Correct 145 ms 40792 KB Output is correct
11 Correct 148 ms 39416 KB Output is correct
12 Correct 92 ms 33324 KB Output is correct
13 Incorrect 157 ms 39104 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #3
0 / 86.0

# 결과 실행 시간 메모리 Grader output
1 Correct 20 ms 23772 KB Output is correct
2 Correct 19 ms 23800 KB Output is correct
3 Correct 19 ms 23800 KB Output is correct
4 Correct 22 ms 23800 KB Output is correct
5 Correct 39 ms 27384 KB Output is correct
6 Correct 39 ms 27512 KB Output is correct
7 Correct 38 ms 27128 KB Output is correct
8 Correct 138 ms 40756 KB Output is correct
9 Correct 144 ms 40912 KB Output is correct
10 Correct 145 ms 40792 KB Output is correct
11 Correct 148 ms 39416 KB Output is correct
12 Correct 92 ms 33324 KB Output is correct
13 Incorrect 157 ms 39104 KB Output isn't correct
14 Halted 0 ms 0 KB -