| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1031623 | 2024-07-23T02:47:26 Z | SamuellH12 | Bitaro’s Party (JOI18_bitaro) | C++17 | 2000 ms | 378704 KB |
#include <bits/stdc++.h>
#define ALL(x) x.begin(), x.end()
#define pii pair<int,int>
const int MAXN = 1e5 + 1;
const int SQRT = 150;
using namespace std;
int block[MAXN], dp[MAXN], order[MAXN], tempo;
vector<int> trafo[MAXN];
vector<pii> best[MAXN];
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int main(){
ios::sync_with_stdio(false);
int n, m, q;
scanf("%d %d %d", &n, &m, &q);
for(int i=0, u, v; i<m; i++)
{
scanf("%d %d", &u, &v);
trafo[v].push_back(u);
dp[u]++;
}
deque<int> fila;
for(int i=1; i<=n; i++) if(!dp[i]) fila.push_back(i);
int od = n;
while(!fila.empty())
{
int u = fila.front(); fila.pop_front();
order[--od] = u;
shuffle(ALL(trafo[u]), rng);
for(int v : trafo[u])
if(--dp[v] == 0)
fila.push_back(v);
}
order[n] = -1;
for(int u : order)
{
if(u == -1) break;
best[u].push_back(pii(0, u));
for(auto v : trafo[u]){
for(auto [x, w] : best[v])
best[u].push_back(pii(x-1, w));
if(best[u].size() >= 1000)
{
sort(ALL(best[u]));
best[u].resize(min(SQRT, (int)(unique(ALL(best[u])) - best[u].begin())));
}
}
sort(ALL(best[u]));
best[u].resize(min(SQRT, (int)(unique(ALL(best[u])) - best[u].begin())));
}
int t, y;
while(q--)
{
tempo++;
scanf("%d %d", &t, &y);
for(int i=0, x; i<y; i++)
{
scanf("%d", &x);
block[x] = tempo;
}
int ans = -1;
for(auto [x, w] : best[t])
if(block[w] != tempo)
{
ans = -x;
break;
}
if(ans == -1) for(int u : order)
{
dp[u] = (block[u] == tempo ? -1 : 0);
for(auto v : trafo[u])
if(~dp[v])
dp[u] = max(dp[u], dp[v]+1);
if(u == t){ ans = dp[u]; break; }
}
printf("%d\n", ans);
}
return 0;
}
Compilation message
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 2 ms | 4956 KB | Output is correct |
| 2 | Correct | 2 ms | 4956 KB | Output is correct |
| 3 | Correct | 2 ms | 4956 KB | Output is correct |
| 4 | Correct | 2 ms | 4956 KB | Output is correct |
| 5 | Correct | 8 ms | 6492 KB | Output is correct |
| 6 | Correct | 8 ms | 6236 KB | Output is correct |
| 7 | Correct | 7 ms | 6524 KB | Output is correct |
| 8 | Correct | 11 ms | 8660 KB | Output is correct |
| 9 | Correct | 11 ms | 8560 KB | Output is correct |
| 10 | Correct | 11 ms | 8540 KB | Output is correct |
| 11 | Correct | 10 ms | 8280 KB | Output is correct |
| 12 | Correct | 9 ms | 7004 KB | Output is correct |
| 13 | Correct | 11 ms | 8436 KB | Output is correct |
| 14 | Correct | 9 ms | 7048 KB | Output is correct |
| 15 | Correct | 6 ms | 6236 KB | Output is correct |
| 16 | Correct | 8 ms | 7004 KB | Output is correct |
| 17 | Correct | 10 ms | 7516 KB | Output is correct |
| 18 | Correct | 7 ms | 6492 KB | Output is correct |
| 19 | Correct | 14 ms | 7488 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 2 ms | 4956 KB | Output is correct |
| 2 | Correct | 2 ms | 4956 KB | Output is correct |
| 3 | Correct | 2 ms | 4956 KB | Output is correct |
| 4 | Correct | 2 ms | 4956 KB | Output is correct |
| 5 | Correct | 8 ms | 6492 KB | Output is correct |
| 6 | Correct | 8 ms | 6236 KB | Output is correct |
| 7 | Correct | 7 ms | 6524 KB | Output is correct |
| 8 | Correct | 11 ms | 8660 KB | Output is correct |
| 9 | Correct | 11 ms | 8560 KB | Output is correct |
| 10 | Correct | 11 ms | 8540 KB | Output is correct |
| 11 | Correct | 10 ms | 8280 KB | Output is correct |
| 12 | Correct | 9 ms | 7004 KB | Output is correct |
| 13 | Correct | 11 ms | 8436 KB | Output is correct |
| 14 | Correct | 9 ms | 7048 KB | Output is correct |
| 15 | Correct | 6 ms | 6236 KB | Output is correct |
| 16 | Correct | 8 ms | 7004 KB | Output is correct |
| 17 | Correct | 10 ms | 7516 KB | Output is correct |
| 18 | Correct | 7 ms | 6492 KB | Output is correct |
| 19 | Correct | 14 ms | 7488 KB | Output is correct |
| 20 | Correct | 1206 ms | 19024 KB | Output is correct |
| 21 | Correct | 1203 ms | 18884 KB | Output is correct |
| 22 | Correct | 1260 ms | 18840 KB | Output is correct |
| 23 | Correct | 1159 ms | 18360 KB | Output is correct |
| 24 | Correct | 1035 ms | 282412 KB | Output is correct |
| 25 | Correct | 1058 ms | 281540 KB | Output is correct |
| 26 | Correct | 1038 ms | 282256 KB | Output is correct |
| 27 | Correct | 958 ms | 376324 KB | Output is correct |
| 28 | Correct | 859 ms | 376292 KB | Output is correct |
| 29 | Correct | 895 ms | 376148 KB | Output is correct |
| 30 | Correct | 964 ms | 375664 KB | Output is correct |
| 31 | Correct | 1069 ms | 352616 KB | Output is correct |
| 32 | Correct | 904 ms | 375464 KB | Output is correct |
| 33 | Correct | 751 ms | 230224 KB | Output is correct |
| 34 | Correct | 741 ms | 195376 KB | Output is correct |
| 35 | Correct | 743 ms | 227920 KB | Output is correct |
| 36 | Correct | 852 ms | 304964 KB | Output is correct |
| 37 | Correct | 865 ms | 271680 KB | Output is correct |
| 38 | Correct | 822 ms | 305744 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 2 ms | 4956 KB | Output is correct |
| 2 | Correct | 2 ms | 4956 KB | Output is correct |
| 3 | Correct | 2 ms | 4956 KB | Output is correct |
| 4 | Correct | 2 ms | 4956 KB | Output is correct |
| 5 | Correct | 8 ms | 6492 KB | Output is correct |
| 6 | Correct | 8 ms | 6236 KB | Output is correct |
| 7 | Correct | 7 ms | 6524 KB | Output is correct |
| 8 | Correct | 11 ms | 8660 KB | Output is correct |
| 9 | Correct | 11 ms | 8560 KB | Output is correct |
| 10 | Correct | 11 ms | 8540 KB | Output is correct |
| 11 | Correct | 10 ms | 8280 KB | Output is correct |
| 12 | Correct | 9 ms | 7004 KB | Output is correct |
| 13 | Correct | 11 ms | 8436 KB | Output is correct |
| 14 | Correct | 9 ms | 7048 KB | Output is correct |
| 15 | Correct | 6 ms | 6236 KB | Output is correct |
| 16 | Correct | 8 ms | 7004 KB | Output is correct |
| 17 | Correct | 10 ms | 7516 KB | Output is correct |
| 18 | Correct | 7 ms | 6492 KB | Output is correct |
| 19 | Correct | 14 ms | 7488 KB | Output is correct |
| 20 | Correct | 1206 ms | 19024 KB | Output is correct |
| 21 | Correct | 1203 ms | 18884 KB | Output is correct |
| 22 | Correct | 1260 ms | 18840 KB | Output is correct |
| 23 | Correct | 1159 ms | 18360 KB | Output is correct |
| 24 | Correct | 1035 ms | 282412 KB | Output is correct |
| 25 | Correct | 1058 ms | 281540 KB | Output is correct |
| 26 | Correct | 1038 ms | 282256 KB | Output is correct |
| 27 | Correct | 958 ms | 376324 KB | Output is correct |
| 28 | Correct | 859 ms | 376292 KB | Output is correct |
| 29 | Correct | 895 ms | 376148 KB | Output is correct |
| 30 | Correct | 964 ms | 375664 KB | Output is correct |
| 31 | Correct | 1069 ms | 352616 KB | Output is correct |
| 32 | Correct | 904 ms | 375464 KB | Output is correct |
| 33 | Correct | 751 ms | 230224 KB | Output is correct |
| 34 | Correct | 741 ms | 195376 KB | Output is correct |
| 35 | Correct | 743 ms | 227920 KB | Output is correct |
| 36 | Correct | 852 ms | 304964 KB | Output is correct |
| 37 | Correct | 865 ms | 271680 KB | Output is correct |
| 38 | Correct | 822 ms | 305744 KB | Output is correct |
| 39 | Correct | 1010 ms | 275024 KB | Output is correct |
| 40 | Correct | 955 ms | 281648 KB | Output is correct |
| 41 | Correct | 1026 ms | 284756 KB | Output is correct |
| 42 | Correct | 988 ms | 279636 KB | Output is correct |
| 43 | Correct | 980 ms | 280184 KB | Output is correct |
| 44 | Correct | 1190 ms | 19516 KB | Output is correct |
| 45 | Correct | 1136 ms | 19280 KB | Output is correct |
| 46 | Correct | 1145 ms | 20308 KB | Output is correct |
| 47 | Correct | 1192 ms | 19836 KB | Output is correct |
| 48 | Correct | 1187 ms | 19976 KB | Output is correct |
| 49 | Correct | 977 ms | 378544 KB | Output is correct |
| 50 | Correct | 1425 ms | 377240 KB | Output is correct |
| 51 | Correct | 1238 ms | 20560 KB | Output is correct |
| 52 | Correct | 1525 ms | 20292 KB | Output is correct |
| 53 | Correct | 908 ms | 306200 KB | Output is correct |
| 54 | Correct | 997 ms | 272720 KB | Output is correct |
| 55 | Correct | 1331 ms | 305872 KB | Output is correct |
| 56 | Correct | 939 ms | 276820 KB | Output is correct |
| 57 | Correct | 1230 ms | 20628 KB | Output is correct |
| 58 | Correct | 1210 ms | 20508 KB | Output is correct |
| 59 | Correct | 1472 ms | 20052 KB | Output is correct |
| 60 | Correct | 1445 ms | 20272 KB | Output is correct |
| 61 | Correct | 980 ms | 377608 KB | Output is correct |
| 62 | Correct | 959 ms | 307704 KB | Output is correct |
| 63 | Correct | 962 ms | 271956 KB | Output is correct |
| 64 | Correct | 1036 ms | 376916 KB | Output is correct |
| 65 | Correct | 1043 ms | 305980 KB | Output is correct |
| 66 | Correct | 1092 ms | 275008 KB | Output is correct |
| 67 | Correct | 1152 ms | 377528 KB | Output is correct |
| 68 | Correct | 1091 ms | 307536 KB | Output is correct |
| 69 | Correct | 1174 ms | 269204 KB | Output is correct |
| 70 | Correct | 893 ms | 376928 KB | Output is correct |
| 71 | Correct | 872 ms | 307120 KB | Output is correct |
| 72 | Correct | 908 ms | 272932 KB | Output is correct |
| 73 | Correct | 878 ms | 376892 KB | Output is correct |
| 74 | Correct | 942 ms | 307284 KB | Output is correct |
| 75 | Correct | 1018 ms | 271620 KB | Output is correct |
| 76 | Correct | 951 ms | 378704 KB | Output is correct |
| 77 | Correct | 903 ms | 378156 KB | Output is correct |
| 78 | Correct | 860 ms | 377752 KB | Output is correct |
| 79 | Correct | 1183 ms | 20820 KB | Output is correct |
| 80 | Correct | 1161 ms | 20396 KB | Output is correct |
| 81 | Correct | 1158 ms | 19920 KB | Output is correct |
| 82 | Correct | 939 ms | 378500 KB | Output is correct |
| 83 | Correct | 1100 ms | 355740 KB | Output is correct |
| 84 | Correct | 934 ms | 377428 KB | Output is correct |
| 85 | Correct | 1040 ms | 353364 KB | Output is correct |
| 86 | Correct | 876 ms | 377284 KB | Output is correct |
| 87 | Correct | 1012 ms | 356132 KB | Output is correct |
| 88 | Correct | 1101 ms | 20960 KB | Output is correct |
| 89 | Correct | 1214 ms | 20500 KB | Output is correct |
| 90 | Correct | 1166 ms | 18904 KB | Output is correct |
| 91 | Correct | 1231 ms | 18788 KB | Output is correct |
| 92 | Correct | 1218 ms | 18916 KB | Output is correct |
| 93 | Correct | 1187 ms | 19028 KB | Output is correct |
| 94 | Correct | 793 ms | 230856 KB | Output is correct |
| 95 | Correct | 768 ms | 194312 KB | Output is correct |
| 96 | Correct | 806 ms | 229288 KB | Output is correct |
| 97 | Correct | 769 ms | 198044 KB | Output is correct |
| 98 | Correct | 791 ms | 230276 KB | Output is correct |
| 99 | Correct | 779 ms | 197716 KB | Output is correct |
| 100 | Correct | 1311 ms | 18880 KB | Output is correct |
| 101 | Correct | 1232 ms | 18768 KB | Output is correct |
| 102 | Correct | 1241 ms | 18640 KB | Output is correct |
| 103 | Correct | 1231 ms | 18572 KB | Output is correct |
| 104 | Correct | 1196 ms | 18384 KB | Output is correct |
| 105 | Correct | 1208 ms | 18440 KB | Output is correct |
| 106 | Correct | 893 ms | 305344 KB | Output is correct |
| 107 | Correct | 948 ms | 274512 KB | Output is correct |
| 108 | Correct | 903 ms | 306836 KB | Output is correct |
| 109 | Correct | 886 ms | 269908 KB | Output is correct |
| 110 | Correct | 807 ms | 308076 KB | Output is correct |
| 111 | Correct | 973 ms | 273116 KB | Output is correct |
| 112 | Correct | 1155 ms | 19304 KB | Output is correct |
| 113 | Correct | 1111 ms | 19284 KB | Output is correct |
| 114 | Correct | 1192 ms | 19024 KB | Output is correct |
| 115 | Correct | 1108 ms | 18720 KB | Output is correct |
| 116 | Correct | 1127 ms | 18844 KB | Output is correct |
| 117 | Correct | 1085 ms | 18836 KB | Output is correct |
| 118 | Execution timed out | 2089 ms | 375820 KB | Time limit exceeded |
| 119 | Halted | 0 ms | 0 KB | - |