oj.uz

Submission #94255

# Submission time Handle Problem Language Result Execution time Memory
94255 2019-01-17T07:02:15 Z autumn_eel Bitaro’s Party (JOI18_bitaro) C++14
7 / 100
 2000 ms 40924 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());
			}
		}
	}
	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]<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: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
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 23848 KB Output is correct
2 Correct 19 ms 23800 KB Output is correct
3 Correct 18 ms 23672 KB Output is correct
4 Correct 18 ms 23800 KB Output is correct
5 Correct 39 ms 27384 KB Output is correct
6 Correct 41 ms 27512 KB Output is correct
7 Correct 38 ms 27212 KB Output is correct
8 Correct 145 ms 40824 KB Output is correct
9 Correct 147 ms 40760 KB Output is correct
10 Correct 143 ms 40924 KB Output is correct
11 Correct 166 ms 39416 KB Output is correct
12 Correct 93 ms 33236 KB Output is correct
13 Correct 164 ms 39132 KB Output is correct
14 Correct 102 ms 33656 KB Output is correct
15 Correct 73 ms 29688 KB Output is correct
16 Correct 113 ms 33528 KB Output is correct
17 Correct 111 ms 35548 KB Output is correct
18 Correct 71 ms 31480 KB Output is correct
19 Correct 102 ms 36088 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 23848 KB Output is correct
2 Correct 19 ms 23800 KB Output is correct
3 Correct 18 ms 23672 KB Output is correct
4 Correct 18 ms 23800 KB Output is correct
5 Correct 39 ms 27384 KB Output is correct
6 Correct 41 ms 27512 KB Output is correct
7 Correct 38 ms 27212 KB Output is correct
8 Correct 145 ms 40824 KB Output is correct
9 Correct 147 ms 40760 KB Output is correct
10 Correct 143 ms 40924 KB Output is correct
11 Correct 166 ms 39416 KB Output is correct
12 Correct 93 ms 33236 KB Output is correct
13 Correct 164 ms 39132 KB Output is correct
14 Correct 102 ms 33656 KB Output is correct
15 Correct 73 ms 29688 KB Output is correct
16 Correct 113 ms 33528 KB Output is correct
17 Correct 111 ms 35548 KB Output is correct
18 Correct 71 ms 31480 KB Output is correct
19 Correct 102 ms 36088 KB Output is correct
20 Execution timed out 2056 ms 38440 KB Time limit exceeded
21 Halted 0 ms 0 KB -

Subtask #3
0 / 86.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 23848 KB Output is correct
2 Correct 19 ms 23800 KB Output is correct
3 Correct 18 ms 23672 KB Output is correct
4 Correct 18 ms 23800 KB Output is correct
5 Correct 39 ms 27384 KB Output is correct
6 Correct 41 ms 27512 KB Output is correct
7 Correct 38 ms 27212 KB Output is correct
8 Correct 145 ms 40824 KB Output is correct
9 Correct 147 ms 40760 KB Output is correct
10 Correct 143 ms 40924 KB Output is correct
11 Correct 166 ms 39416 KB Output is correct
12 Correct 93 ms 33236 KB Output is correct
13 Correct 164 ms 39132 KB Output is correct
14 Correct 102 ms 33656 KB Output is correct
15 Correct 73 ms 29688 KB Output is correct
16 Correct 113 ms 33528 KB Output is correct
17 Correct 111 ms 35548 KB Output is correct
18 Correct 71 ms 31480 KB Output is correct
19 Correct 102 ms 36088 KB Output is correct
20 Execution timed out 2056 ms 38440 KB Time limit exceeded
21 Halted 0 ms 0 KB -