# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
94260 | 2019-01-17T07:15:36 Z | autumn_eel | Bitaro’s Party (JOI18_bitaro) | C++14 | 2000 ms | 131588 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 10 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){ while(dp[i].size()>B)dp[i].erase(dp[i].begin()); 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)); } } } } 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
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 23 ms | 23924 KB | Output is correct |
2 | Correct | 22 ms | 23800 KB | Output is correct |
3 | Correct | 22 ms | 23800 KB | Output is correct |
4 | Correct | 22 ms | 23800 KB | Output is correct |
5 | Correct | 27 ms | 24696 KB | Output is correct |
6 | Correct | 27 ms | 24696 KB | Output is correct |
7 | Correct | 28 ms | 24696 KB | Output is correct |
8 | Correct | 27 ms | 24880 KB | Output is correct |
9 | Correct | 27 ms | 24824 KB | Output is correct |
10 | Correct | 27 ms | 24824 KB | Output is correct |
11 | Correct | 27 ms | 24824 KB | Output is correct |
12 | Correct | 29 ms | 24824 KB | Output is correct |
13 | Correct | 28 ms | 24828 KB | Output is correct |
14 | Correct | 27 ms | 24568 KB | Output is correct |
15 | Correct | 27 ms | 24696 KB | Output is correct |
16 | Correct | 27 ms | 24696 KB | Output is correct |
17 | Correct | 27 ms | 24696 KB | Output is correct |
18 | Correct | 28 ms | 24696 KB | Output is correct |
19 | Correct | 26 ms | 24696 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 23 ms | 23924 KB | Output is correct |
2 | Correct | 22 ms | 23800 KB | Output is correct |
3 | Correct | 22 ms | 23800 KB | Output is correct |
4 | Correct | 22 ms | 23800 KB | Output is correct |
5 | Correct | 27 ms | 24696 KB | Output is correct |
6 | Correct | 27 ms | 24696 KB | Output is correct |
7 | Correct | 28 ms | 24696 KB | Output is correct |
8 | Correct | 27 ms | 24880 KB | Output is correct |
9 | Correct | 27 ms | 24824 KB | Output is correct |
10 | Correct | 27 ms | 24824 KB | Output is correct |
11 | Correct | 27 ms | 24824 KB | Output is correct |
12 | Correct | 29 ms | 24824 KB | Output is correct |
13 | Correct | 28 ms | 24828 KB | Output is correct |
14 | Correct | 27 ms | 24568 KB | Output is correct |
15 | Correct | 27 ms | 24696 KB | Output is correct |
16 | Correct | 27 ms | 24696 KB | Output is correct |
17 | Correct | 27 ms | 24696 KB | Output is correct |
18 | Correct | 28 ms | 24696 KB | Output is correct |
19 | Correct | 26 ms | 24696 KB | Output is correct |
20 | Correct | 428 ms | 25924 KB | Output is correct |
21 | Correct | 463 ms | 26064 KB | Output is correct |
22 | Correct | 404 ms | 25976 KB | Output is correct |
23 | Correct | 430 ms | 26360 KB | Output is correct |
24 | Correct | 809 ms | 109560 KB | Output is correct |
25 | Correct | 978 ms | 113356 KB | Output is correct |
26 | Correct | 833 ms | 110200 KB | Output is correct |
27 | Correct | 836 ms | 124156 KB | Output is correct |
28 | Correct | 745 ms | 124024 KB | Output is correct |
29 | Correct | 715 ms | 124040 KB | Output is correct |
30 | Correct | 703 ms | 123640 KB | Output is correct |
31 | Correct | 885 ms | 131588 KB | Output is correct |
32 | Correct | 708 ms | 123484 KB | Output is correct |
33 | Correct | 726 ms | 105516 KB | Output is correct |
34 | Correct | 911 ms | 118136 KB | Output is correct |
35 | Correct | 815 ms | 105656 KB | Output is correct |
36 | Correct | 753 ms | 110772 KB | Output is correct |
37 | Correct | 919 ms | 114960 KB | Output is correct |
38 | Correct | 806 ms | 110904 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 23 ms | 23924 KB | Output is correct |
2 | Correct | 22 ms | 23800 KB | Output is correct |
3 | Correct | 22 ms | 23800 KB | Output is correct |
4 | Correct | 22 ms | 23800 KB | Output is correct |
5 | Correct | 27 ms | 24696 KB | Output is correct |
6 | Correct | 27 ms | 24696 KB | Output is correct |
7 | Correct | 28 ms | 24696 KB | Output is correct |
8 | Correct | 27 ms | 24880 KB | Output is correct |
9 | Correct | 27 ms | 24824 KB | Output is correct |
10 | Correct | 27 ms | 24824 KB | Output is correct |
11 | Correct | 27 ms | 24824 KB | Output is correct |
12 | Correct | 29 ms | 24824 KB | Output is correct |
13 | Correct | 28 ms | 24828 KB | Output is correct |
14 | Correct | 27 ms | 24568 KB | Output is correct |
15 | Correct | 27 ms | 24696 KB | Output is correct |
16 | Correct | 27 ms | 24696 KB | Output is correct |
17 | Correct | 27 ms | 24696 KB | Output is correct |
18 | Correct | 28 ms | 24696 KB | Output is correct |
19 | Correct | 26 ms | 24696 KB | Output is correct |
20 | Correct | 428 ms | 25924 KB | Output is correct |
21 | Correct | 463 ms | 26064 KB | Output is correct |
22 | Correct | 404 ms | 25976 KB | Output is correct |
23 | Correct | 430 ms | 26360 KB | Output is correct |
24 | Correct | 809 ms | 109560 KB | Output is correct |
25 | Correct | 978 ms | 113356 KB | Output is correct |
26 | Correct | 833 ms | 110200 KB | Output is correct |
27 | Correct | 836 ms | 124156 KB | Output is correct |
28 | Correct | 745 ms | 124024 KB | Output is correct |
29 | Correct | 715 ms | 124040 KB | Output is correct |
30 | Correct | 703 ms | 123640 KB | Output is correct |
31 | Correct | 885 ms | 131588 KB | Output is correct |
32 | Correct | 708 ms | 123484 KB | Output is correct |
33 | Correct | 726 ms | 105516 KB | Output is correct |
34 | Correct | 911 ms | 118136 KB | Output is correct |
35 | Correct | 815 ms | 105656 KB | Output is correct |
36 | Correct | 753 ms | 110772 KB | Output is correct |
37 | Correct | 919 ms | 114960 KB | Output is correct |
38 | Correct | 806 ms | 110904 KB | Output is correct |
39 | Correct | 1097 ms | 109072 KB | Output is correct |
40 | Execution timed out | 2087 ms | 110456 KB | Time limit exceeded |
41 | Halted | 0 ms | 0 KB | - |