| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1031625 | 2024-07-23T02:48:00 Z | SamuellH12 | Bitaro’s Party (JOI18_bitaro) | C++17 | 2000 ms | 195300 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 = 75;
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
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 2 ms | 4952 KB | Output is correct |
| 2 | Correct | 2 ms | 4956 KB | Output is correct |
| 3 | Correct | 2 ms | 5164 KB | Output is correct |
| 4 | Correct | 2 ms | 4956 KB | Output is correct |
| 5 | Correct | 6 ms | 6232 KB | Output is correct |
| 6 | Correct | 5 ms | 5960 KB | Output is correct |
| 7 | Correct | 6 ms | 5976 KB | Output is correct |
| 8 | Correct | 7 ms | 7004 KB | Output is correct |
| 9 | Correct | 6 ms | 6916 KB | Output is correct |
| 10 | Correct | 7 ms | 6804 KB | Output is correct |
| 11 | Correct | 8 ms | 6748 KB | Output is correct |
| 12 | Correct | 6 ms | 6276 KB | Output is correct |
| 13 | Correct | 7 ms | 6748 KB | Output is correct |
| 14 | Correct | 7 ms | 6212 KB | Output is correct |
| 15 | Correct | 5 ms | 5720 KB | Output is correct |
| 16 | Correct | 6 ms | 6236 KB | Output is correct |
| 17 | Correct | 6 ms | 6492 KB | Output is correct |
| 18 | Correct | 8 ms | 5980 KB | Output is correct |
| 19 | Correct | 6 ms | 6492 KB | Output is correct |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 2 ms | 4952 KB | Output is correct |
| 2 | Correct | 2 ms | 4956 KB | Output is correct |
| 3 | Correct | 2 ms | 5164 KB | Output is correct |
| 4 | Correct | 2 ms | 4956 KB | Output is correct |
| 5 | Correct | 6 ms | 6232 KB | Output is correct |
| 6 | Correct | 5 ms | 5960 KB | Output is correct |
| 7 | Correct | 6 ms | 5976 KB | Output is correct |
| 8 | Correct | 7 ms | 7004 KB | Output is correct |
| 9 | Correct | 6 ms | 6916 KB | Output is correct |
| 10 | Correct | 7 ms | 6804 KB | Output is correct |
| 11 | Correct | 8 ms | 6748 KB | Output is correct |
| 12 | Correct | 6 ms | 6276 KB | Output is correct |
| 13 | Correct | 7 ms | 6748 KB | Output is correct |
| 14 | Correct | 7 ms | 6212 KB | Output is correct |
| 15 | Correct | 5 ms | 5720 KB | Output is correct |
| 16 | Correct | 6 ms | 6236 KB | Output is correct |
| 17 | Correct | 6 ms | 6492 KB | Output is correct |
| 18 | Correct | 8 ms | 5980 KB | Output is correct |
| 19 | Correct | 6 ms | 6492 KB | Output is correct |
| 20 | Correct | 601 ms | 19340 KB | Output is correct |
| 21 | Correct | 591 ms | 19508 KB | Output is correct |
| 22 | Correct | 608 ms | 19452 KB | Output is correct |
| 23 | Correct | 596 ms | 19020 KB | Output is correct |
| 24 | Correct | 570 ms | 153288 KB | Output is correct |
| 25 | Correct | 524 ms | 152656 KB | Output is correct |
| 26 | Correct | 551 ms | 153204 KB | Output is correct |
| 27 | Correct | 452 ms | 195292 KB | Output is correct |
| 28 | Correct | 485 ms | 195300 KB | Output is correct |
| 29 | Correct | 467 ms | 195156 KB | Output is correct |
| 30 | Correct | 504 ms | 195108 KB | Output is correct |
| 31 | Correct | 520 ms | 186192 KB | Output is correct |
| 32 | Correct | 472 ms | 194932 KB | Output is correct |
| 33 | Correct | 386 ms | 125352 KB | Output is correct |
| 34 | Correct | 420 ms | 111756 KB | Output is correct |
| 35 | Correct | 380 ms | 124440 KB | Output is correct |
| 36 | Correct | 431 ms | 159956 KB | Output is correct |
| 37 | Correct | 480 ms | 146608 KB | Output is correct |
| 38 | Correct | 430 ms | 160080 KB | Output is correct |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 2 ms | 4952 KB | Output is correct |
| 2 | Correct | 2 ms | 4956 KB | Output is correct |
| 3 | Correct | 2 ms | 5164 KB | Output is correct |
| 4 | Correct | 2 ms | 4956 KB | Output is correct |
| 5 | Correct | 6 ms | 6232 KB | Output is correct |
| 6 | Correct | 5 ms | 5960 KB | Output is correct |
| 7 | Correct | 6 ms | 5976 KB | Output is correct |
| 8 | Correct | 7 ms | 7004 KB | Output is correct |
| 9 | Correct | 6 ms | 6916 KB | Output is correct |
| 10 | Correct | 7 ms | 6804 KB | Output is correct |
| 11 | Correct | 8 ms | 6748 KB | Output is correct |
| 12 | Correct | 6 ms | 6276 KB | Output is correct |
| 13 | Correct | 7 ms | 6748 KB | Output is correct |
| 14 | Correct | 7 ms | 6212 KB | Output is correct |
| 15 | Correct | 5 ms | 5720 KB | Output is correct |
| 16 | Correct | 6 ms | 6236 KB | Output is correct |
| 17 | Correct | 6 ms | 6492 KB | Output is correct |
| 18 | Correct | 8 ms | 5980 KB | Output is correct |
| 19 | Correct | 6 ms | 6492 KB | Output is correct |
| 20 | Correct | 601 ms | 19340 KB | Output is correct |
| 21 | Correct | 591 ms | 19508 KB | Output is correct |
| 22 | Correct | 608 ms | 19452 KB | Output is correct |
| 23 | Correct | 596 ms | 19020 KB | Output is correct |
| 24 | Correct | 570 ms | 153288 KB | Output is correct |
| 25 | Correct | 524 ms | 152656 KB | Output is correct |
| 26 | Correct | 551 ms | 153204 KB | Output is correct |
| 27 | Correct | 452 ms | 195292 KB | Output is correct |
| 28 | Correct | 485 ms | 195300 KB | Output is correct |
| 29 | Correct | 467 ms | 195156 KB | Output is correct |
| 30 | Correct | 504 ms | 195108 KB | Output is correct |
| 31 | Correct | 520 ms | 186192 KB | Output is correct |
| 32 | Correct | 472 ms | 194932 KB | Output is correct |
| 33 | Correct | 386 ms | 125352 KB | Output is correct |
| 34 | Correct | 420 ms | 111756 KB | Output is correct |
| 35 | Correct | 380 ms | 124440 KB | Output is correct |
| 36 | Correct | 431 ms | 159956 KB | Output is correct |
| 37 | Correct | 480 ms | 146608 KB | Output is correct |
| 38 | Correct | 430 ms | 160080 KB | Output is correct |
| 39 | Correct | 572 ms | 151864 KB | Output is correct |
| 40 | Correct | 535 ms | 152300 KB | Output is correct |
| 41 | Correct | 559 ms | 153936 KB | Output is correct |
| 42 | Correct | 555 ms | 153680 KB | Output is correct |
| 43 | Correct | 546 ms | 152912 KB | Output is correct |
| 44 | Correct | 617 ms | 20248 KB | Output is correct |
| 45 | Correct | 603 ms | 19536 KB | Output is correct |
| 46 | Correct | 585 ms | 18512 KB | Output is correct |
| 47 | Correct | 591 ms | 18516 KB | Output is correct |
| 48 | Correct | 584 ms | 18468 KB | Output is correct |
| 49 | Correct | 522 ms | 194104 KB | Output is correct |
| 50 | Correct | 970 ms | 193384 KB | Output is correct |
| 51 | Correct | 591 ms | 18752 KB | Output is correct |
| 52 | Correct | 845 ms | 18560 KB | Output is correct |
| 53 | Correct | 488 ms | 158068 KB | Output is correct |
| 54 | Correct | 504 ms | 145236 KB | Output is correct |
| 55 | Correct | 896 ms | 157532 KB | Output is correct |
| 56 | Correct | 734 ms | 147004 KB | Output is correct |
| 57 | Correct | 642 ms | 18756 KB | Output is correct |
| 58 | Correct | 645 ms | 18676 KB | Output is correct |
| 59 | Correct | 868 ms | 18428 KB | Output is correct |
| 60 | Correct | 860 ms | 18548 KB | Output is correct |
| 61 | Correct | 462 ms | 193364 KB | Output is correct |
| 62 | Correct | 484 ms | 158648 KB | Output is correct |
| 63 | Correct | 517 ms | 144524 KB | Output is correct |
| 64 | Correct | 629 ms | 192988 KB | Output is correct |
| 65 | Correct | 603 ms | 157780 KB | Output is correct |
| 66 | Correct | 659 ms | 145904 KB | Output is correct |
| 67 | Correct | 691 ms | 193380 KB | Output is correct |
| 68 | Correct | 691 ms | 158572 KB | Output is correct |
| 69 | Correct | 748 ms | 143452 KB | Output is correct |
| 70 | Correct | 422 ms | 193104 KB | Output is correct |
| 71 | Correct | 467 ms | 158444 KB | Output is correct |
| 72 | Correct | 472 ms | 144720 KB | Output is correct |
| 73 | Correct | 467 ms | 193168 KB | Output is correct |
| 74 | Correct | 425 ms | 158292 KB | Output is correct |
| 75 | Correct | 507 ms | 144360 KB | Output is correct |
| 76 | Correct | 477 ms | 194272 KB | Output is correct |
| 77 | Correct | 453 ms | 193752 KB | Output is correct |
| 78 | Correct | 454 ms | 193760 KB | Output is correct |
| 79 | Correct | 565 ms | 18760 KB | Output is correct |
| 80 | Correct | 556 ms | 18548 KB | Output is correct |
| 81 | Correct | 566 ms | 18524 KB | Output is correct |
| 82 | Correct | 495 ms | 194268 KB | Output is correct |
| 83 | Correct | 564 ms | 185500 KB | Output is correct |
| 84 | Correct | 422 ms | 193756 KB | Output is correct |
| 85 | Correct | 516 ms | 184400 KB | Output is correct |
| 86 | Correct | 443 ms | 193360 KB | Output is correct |
| 87 | Correct | 490 ms | 185428 KB | Output is correct |
| 88 | Correct | 553 ms | 18768 KB | Output is correct |
| 89 | Correct | 609 ms | 19316 KB | Output is correct |
| 90 | Correct | 614 ms | 19524 KB | Output is correct |
| 91 | Correct | 590 ms | 19632 KB | Output is correct |
| 92 | Correct | 604 ms | 19536 KB | Output is correct |
| 93 | Correct | 583 ms | 19432 KB | Output is correct |
| 94 | Correct | 452 ms | 126480 KB | Output is correct |
| 95 | Correct | 435 ms | 112088 KB | Output is correct |
| 96 | Correct | 417 ms | 125264 KB | Output is correct |
| 97 | Correct | 412 ms | 113712 KB | Output is correct |
| 98 | Correct | 382 ms | 126044 KB | Output is correct |
| 99 | Correct | 405 ms | 113160 KB | Output is correct |
| 100 | Correct | 606 ms | 19956 KB | Output is correct |
| 101 | Correct | 632 ms | 19768 KB | Output is correct |
| 102 | Correct | 595 ms | 19280 KB | Output is correct |
| 103 | Correct | 617 ms | 19160 KB | Output is correct |
| 104 | Correct | 612 ms | 19028 KB | Output is correct |
| 105 | Correct | 625 ms | 19028 KB | Output is correct |
| 106 | Correct | 567 ms | 160592 KB | Output is correct |
| 107 | Correct | 516 ms | 148820 KB | Output is correct |
| 108 | Correct | 483 ms | 160852 KB | Output is correct |
| 109 | Correct | 500 ms | 145904 KB | Output is correct |
| 110 | Correct | 457 ms | 161604 KB | Output is correct |
| 111 | Correct | 495 ms | 147536 KB | Output is correct |
| 112 | Correct | 617 ms | 20384 KB | Output is correct |
| 113 | Correct | 599 ms | 20472 KB | Output is correct |
| 114 | Correct | 612 ms | 19796 KB | Output is correct |
| 115 | Correct | 612 ms | 19684 KB | Output is correct |
| 116 | Correct | 607 ms | 19460 KB | Output is correct |
| 117 | Correct | 582 ms | 19428 KB | Output is correct |
| 118 | Execution timed out | 2076 ms | 194712 KB | Time limit exceeded |
| 119 | Halted | 0 ms | 0 KB | - |