# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
227440 | 2020-04-27T12:33:02 Z | MKopchev | Bitaro’s Party (JOI18_bitaro) | C++14 | 1708 ms | 120184 KB |
#include<bits/stdc++.h> using namespace std; const int nmax=1e5+42,CUT=100; vector<int> adj[nmax],bck[nmax]; int n,m,q; int sz,where; int blocked[nmax]; bool is_blocked[nmax]; int dp[nmax]; int slow() { for(int i=1;i<=n;i++) dp[i]=-1e9; dp[where]=0; for(int i=where-1;i>=1;i--) { for(auto k:adj[i]) dp[i]=max(dp[i],dp[k]+1); } int mx=-1; for(int i=where;i>=1;i--) if(is_blocked[i]==0)mx=max(mx,dp[i]); return mx; } vector< pair<int/*distance*/,int/*start*/> > best[nmax]; int main() { scanf("%i%i%i",&n,&m,&q); for(int i=1;i<=m;i++) { int u,v; scanf("%i%i",&u,&v); adj[u].push_back(v); bck[v].push_back(u); } vector< pair<int/*distance*/,int/*start*/> > help={}; for(int i=1;i<=n;i++) { help={}; for(auto node_back:bck[i]) for(auto k:best[node_back]) help.push_back({k.first+1,k.second}); help.push_back({0,i}); sort(help.begin(),help.end()); reverse(help.begin(),help.end()); for(auto k:help) { if(is_blocked[k.second]==0) { is_blocked[k.second]=1; best[i].push_back(k); if(best[i].size()==CUT)break; } } for(auto k:best[i]) is_blocked[k.second]=0; } for(int i=1;i<=q;i++) { scanf("%i%i",&where,&sz); for(int j=1;j<=sz;j++) { scanf("%i",&blocked[j]); is_blocked[blocked[j]]=1; } if(sz>=CUT)printf("%i\n",slow()); else { int mx=-1; for(auto k:best[where]) if(is_blocked[k.second]==0)mx=max(mx,k.first); printf("%i\n",mx); } for(int j=1;j<=sz;j++) { is_blocked[blocked[j]]=0; } } return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 9 ms | 7424 KB | Output is correct |
2 | Correct | 9 ms | 7424 KB | Output is correct |
3 | Correct | 8 ms | 7424 KB | Output is correct |
4 | Correct | 10 ms | 7424 KB | Output is correct |
5 | Correct | 13 ms | 7808 KB | Output is correct |
6 | Correct | 13 ms | 7808 KB | Output is correct |
7 | Correct | 12 ms | 7808 KB | Output is correct |
8 | Correct | 16 ms | 8448 KB | Output is correct |
9 | Correct | 17 ms | 8448 KB | Output is correct |
10 | Correct | 17 ms | 8448 KB | Output is correct |
11 | Correct | 18 ms | 8448 KB | Output is correct |
12 | Correct | 16 ms | 8192 KB | Output is correct |
13 | Correct | 17 ms | 8320 KB | Output is correct |
14 | Correct | 15 ms | 8064 KB | Output is correct |
15 | Correct | 13 ms | 7936 KB | Output is correct |
16 | Correct | 16 ms | 8064 KB | Output is correct |
17 | Correct | 17 ms | 8192 KB | Output is correct |
18 | Correct | 15 ms | 8064 KB | Output is correct |
19 | Correct | 18 ms | 8192 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 9 ms | 7424 KB | Output is correct |
2 | Correct | 9 ms | 7424 KB | Output is correct |
3 | Correct | 8 ms | 7424 KB | Output is correct |
4 | Correct | 10 ms | 7424 KB | Output is correct |
5 | Correct | 13 ms | 7808 KB | Output is correct |
6 | Correct | 13 ms | 7808 KB | Output is correct |
7 | Correct | 12 ms | 7808 KB | Output is correct |
8 | Correct | 16 ms | 8448 KB | Output is correct |
9 | Correct | 17 ms | 8448 KB | Output is correct |
10 | Correct | 17 ms | 8448 KB | Output is correct |
11 | Correct | 18 ms | 8448 KB | Output is correct |
12 | Correct | 16 ms | 8192 KB | Output is correct |
13 | Correct | 17 ms | 8320 KB | Output is correct |
14 | Correct | 15 ms | 8064 KB | Output is correct |
15 | Correct | 13 ms | 7936 KB | Output is correct |
16 | Correct | 16 ms | 8064 KB | Output is correct |
17 | Correct | 17 ms | 8192 KB | Output is correct |
18 | Correct | 15 ms | 8064 KB | Output is correct |
19 | Correct | 18 ms | 8192 KB | Output is correct |
20 | Correct | 1572 ms | 10988 KB | Output is correct |
21 | Correct | 1553 ms | 10856 KB | Output is correct |
22 | Correct | 1551 ms | 10924 KB | Output is correct |
23 | Correct | 1529 ms | 11648 KB | Output is correct |
24 | Correct | 1020 ms | 90872 KB | Output is correct |
25 | Correct | 1061 ms | 92328 KB | Output is correct |
26 | Correct | 1062 ms | 92152 KB | Output is correct |
27 | Correct | 862 ms | 116404 KB | Output is correct |
28 | Correct | 844 ms | 116472 KB | Output is correct |
29 | Correct | 846 ms | 116344 KB | Output is correct |
30 | Correct | 1016 ms | 115836 KB | Output is correct |
31 | Correct | 1068 ms | 114024 KB | Output is correct |
32 | Correct | 1010 ms | 116232 KB | Output is correct |
33 | Correct | 811 ms | 78692 KB | Output is correct |
34 | Correct | 817 ms | 72024 KB | Output is correct |
35 | Correct | 805 ms | 78192 KB | Output is correct |
36 | Correct | 959 ms | 97436 KB | Output is correct |
37 | Correct | 950 ms | 93332 KB | Output is correct |
38 | Correct | 958 ms | 97756 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 9 ms | 7424 KB | Output is correct |
2 | Correct | 9 ms | 7424 KB | Output is correct |
3 | Correct | 8 ms | 7424 KB | Output is correct |
4 | Correct | 10 ms | 7424 KB | Output is correct |
5 | Correct | 13 ms | 7808 KB | Output is correct |
6 | Correct | 13 ms | 7808 KB | Output is correct |
7 | Correct | 12 ms | 7808 KB | Output is correct |
8 | Correct | 16 ms | 8448 KB | Output is correct |
9 | Correct | 17 ms | 8448 KB | Output is correct |
10 | Correct | 17 ms | 8448 KB | Output is correct |
11 | Correct | 18 ms | 8448 KB | Output is correct |
12 | Correct | 16 ms | 8192 KB | Output is correct |
13 | Correct | 17 ms | 8320 KB | Output is correct |
14 | Correct | 15 ms | 8064 KB | Output is correct |
15 | Correct | 13 ms | 7936 KB | Output is correct |
16 | Correct | 16 ms | 8064 KB | Output is correct |
17 | Correct | 17 ms | 8192 KB | Output is correct |
18 | Correct | 15 ms | 8064 KB | Output is correct |
19 | Correct | 18 ms | 8192 KB | Output is correct |
20 | Correct | 1572 ms | 10988 KB | Output is correct |
21 | Correct | 1553 ms | 10856 KB | Output is correct |
22 | Correct | 1551 ms | 10924 KB | Output is correct |
23 | Correct | 1529 ms | 11648 KB | Output is correct |
24 | Correct | 1020 ms | 90872 KB | Output is correct |
25 | Correct | 1061 ms | 92328 KB | Output is correct |
26 | Correct | 1062 ms | 92152 KB | Output is correct |
27 | Correct | 862 ms | 116404 KB | Output is correct |
28 | Correct | 844 ms | 116472 KB | Output is correct |
29 | Correct | 846 ms | 116344 KB | Output is correct |
30 | Correct | 1016 ms | 115836 KB | Output is correct |
31 | Correct | 1068 ms | 114024 KB | Output is correct |
32 | Correct | 1010 ms | 116232 KB | Output is correct |
33 | Correct | 811 ms | 78692 KB | Output is correct |
34 | Correct | 817 ms | 72024 KB | Output is correct |
35 | Correct | 805 ms | 78192 KB | Output is correct |
36 | Correct | 959 ms | 97436 KB | Output is correct |
37 | Correct | 950 ms | 93332 KB | Output is correct |
38 | Correct | 958 ms | 97756 KB | Output is correct |
39 | Correct | 1106 ms | 91640 KB | Output is correct |
40 | Correct | 1146 ms | 94328 KB | Output is correct |
41 | Correct | 1702 ms | 94584 KB | Output is correct |
42 | Correct | 1220 ms | 94524 KB | Output is correct |
43 | Correct | 1080 ms | 94072 KB | Output is correct |
44 | Correct | 1642 ms | 14028 KB | Output is correct |
45 | Correct | 1605 ms | 13172 KB | Output is correct |
46 | Correct | 1685 ms | 12944 KB | Output is correct |
47 | Correct | 1613 ms | 12736 KB | Output is correct |
48 | Correct | 1597 ms | 12564 KB | Output is correct |
49 | Correct | 964 ms | 119660 KB | Output is correct |
50 | Correct | 1449 ms | 118836 KB | Output is correct |
51 | Correct | 1608 ms | 13556 KB | Output is correct |
52 | Correct | 1663 ms | 12892 KB | Output is correct |
53 | Correct | 978 ms | 99832 KB | Output is correct |
54 | Correct | 993 ms | 95852 KB | Output is correct |
55 | Correct | 1400 ms | 99196 KB | Output is correct |
56 | Correct | 1435 ms | 95732 KB | Output is correct |
57 | Correct | 1628 ms | 13768 KB | Output is correct |
58 | Correct | 1633 ms | 14068 KB | Output is correct |
59 | Correct | 1684 ms | 12976 KB | Output is correct |
60 | Correct | 1692 ms | 13256 KB | Output is correct |
61 | Correct | 958 ms | 119032 KB | Output is correct |
62 | Correct | 1006 ms | 99832 KB | Output is correct |
63 | Correct | 1012 ms | 95028 KB | Output is correct |
64 | Correct | 1160 ms | 118944 KB | Output is correct |
65 | Correct | 1382 ms | 99448 KB | Output is correct |
66 | Correct | 1381 ms | 95748 KB | Output is correct |
67 | Correct | 1323 ms | 119000 KB | Output is correct |
68 | Correct | 1562 ms | 99832 KB | Output is correct |
69 | Correct | 1391 ms | 94576 KB | Output is correct |
70 | Correct | 903 ms | 118960 KB | Output is correct |
71 | Correct | 918 ms | 99696 KB | Output is correct |
72 | Correct | 945 ms | 95396 KB | Output is correct |
73 | Correct | 993 ms | 118904 KB | Output is correct |
74 | Correct | 1000 ms | 99704 KB | Output is correct |
75 | Correct | 939 ms | 95368 KB | Output is correct |
76 | Correct | 928 ms | 120184 KB | Output is correct |
77 | Correct | 1326 ms | 119356 KB | Output is correct |
78 | Correct | 862 ms | 119416 KB | Output is correct |
79 | Correct | 1611 ms | 13812 KB | Output is correct |
80 | Correct | 1654 ms | 13044 KB | Output is correct |
81 | Correct | 1559 ms | 12640 KB | Output is correct |
82 | Correct | 1035 ms | 119444 KB | Output is correct |
83 | Correct | 1105 ms | 117440 KB | Output is correct |
84 | Correct | 1432 ms | 118620 KB | Output is correct |
85 | Correct | 1497 ms | 116728 KB | Output is correct |
86 | Correct | 948 ms | 118648 KB | Output is correct |
87 | Correct | 1042 ms | 116728 KB | Output is correct |
88 | Correct | 1642 ms | 13784 KB | Output is correct |
89 | Correct | 1643 ms | 14148 KB | Output is correct |
90 | Correct | 1677 ms | 12964 KB | Output is correct |
91 | Correct | 1697 ms | 12912 KB | Output is correct |
92 | Correct | 1570 ms | 12532 KB | Output is correct |
93 | Correct | 1569 ms | 12560 KB | Output is correct |
94 | Correct | 852 ms | 81912 KB | Output is correct |
95 | Correct | 814 ms | 74724 KB | Output is correct |
96 | Correct | 1211 ms | 80632 KB | Output is correct |
97 | Correct | 1196 ms | 75164 KB | Output is correct |
98 | Correct | 811 ms | 81060 KB | Output is correct |
99 | Correct | 761 ms | 74692 KB | Output is correct |
100 | Correct | 1630 ms | 14168 KB | Output is correct |
101 | Correct | 1596 ms | 13980 KB | Output is correct |
102 | Correct | 1676 ms | 13184 KB | Output is correct |
103 | Correct | 1638 ms | 13468 KB | Output is correct |
104 | Correct | 1562 ms | 12716 KB | Output is correct |
105 | Correct | 1600 ms | 13292 KB | Output is correct |
106 | Correct | 1054 ms | 100344 KB | Output is correct |
107 | Correct | 1012 ms | 96308 KB | Output is correct |
108 | Correct | 1392 ms | 100088 KB | Output is correct |
109 | Correct | 1446 ms | 95492 KB | Output is correct |
110 | Correct | 929 ms | 100088 KB | Output is correct |
111 | Correct | 951 ms | 96092 KB | Output is correct |
112 | Correct | 1636 ms | 13940 KB | Output is correct |
113 | Correct | 1633 ms | 14276 KB | Output is correct |
114 | Correct | 1662 ms | 13056 KB | Output is correct |
115 | Correct | 1708 ms | 13156 KB | Output is correct |
116 | Correct | 1587 ms | 12532 KB | Output is correct |
117 | Correct | 1575 ms | 12928 KB | Output is correct |
118 | Correct | 941 ms | 118776 KB | Output is correct |
119 | Correct | 951 ms | 99448 KB | Output is correct |
120 | Correct | 977 ms | 94736 KB | Output is correct |
121 | Correct | 882 ms | 118576 KB | Output is correct |
122 | Correct | 990 ms | 99200 KB | Output is correct |
123 | Correct | 969 ms | 94580 KB | Output is correct |
124 | Correct | 851 ms | 118392 KB | Output is correct |
125 | Correct | 953 ms | 99536 KB | Output is correct |
126 | Correct | 962 ms | 94780 KB | Output is correct |