| Task: | Microservice hell |
| Sender: | aalto2024g_002 |
| Submission time: | 2024-10-09 16:28:46 +0300 |
| Language: | C++ (C++11) |
| Status: | READY |
| Result: | WRONG ANSWER |
| test | verdict | time | |
|---|---|---|---|
| #1 | WRONG ANSWER | 0.01 s | details |
| #2 | WRONG ANSWER | 0.01 s | details |
| #3 | WRONG ANSWER | 0.01 s | details |
| #4 | WRONG ANSWER | 0.01 s | details |
| #5 | WRONG ANSWER | 0.01 s | details |
| #6 | WRONG ANSWER | 0.01 s | details |
| #7 | WRONG ANSWER | 0.01 s | details |
| #8 | WRONG ANSWER | 0.01 s | details |
| #9 | WRONG ANSWER | 0.01 s | details |
| #10 | WRONG ANSWER | 0.01 s | details |
| #11 | WRONG ANSWER | 0.01 s | details |
| #12 | WRONG ANSWER | 0.01 s | details |
| #13 | WRONG ANSWER | 0.01 s | details |
| #14 | WRONG ANSWER | 0.01 s | details |
| #15 | WRONG ANSWER | 0.01 s | details |
| #16 | WRONG ANSWER | 0.01 s | details |
| #17 | WRONG ANSWER | 0.01 s | details |
| #18 | WRONG ANSWER | 0.01 s | details |
| #19 | WRONG ANSWER | 0.01 s | details |
| #20 | WRONG ANSWER | 0.01 s | details |
| #21 | WRONG ANSWER | 0.01 s | details |
| #22 | WRONG ANSWER | 0.01 s | details |
| #23 | WRONG ANSWER | 0.01 s | details |
| #24 | WRONG ANSWER | 0.01 s | details |
| #25 | WRONG ANSWER | 0.01 s | details |
| #26 | WRONG ANSWER | 0.01 s | details |
| #27 | WRONG ANSWER | 0.01 s | details |
| #28 | WRONG ANSWER | 0.01 s | details |
| #29 | WRONG ANSWER | 0.01 s | details |
| #30 | WRONG ANSWER | 0.01 s | details |
| #31 | WRONG ANSWER | 0.01 s | details |
| #32 | WRONG ANSWER | 0.01 s | details |
| #33 | WRONG ANSWER | 0.01 s | details |
| #34 | WRONG ANSWER | 0.01 s | details |
| #35 | WRONG ANSWER | 0.01 s | details |
| #36 | WRONG ANSWER | 0.01 s | details |
| #37 | WRONG ANSWER | 0.01 s | details |
| #38 | WRONG ANSWER | 0.01 s | details |
| #39 | WRONG ANSWER | 0.01 s | details |
| #40 | WRONG ANSWER | 0.01 s | details |
| #41 | WRONG ANSWER | 0.01 s | details |
| #42 | WRONG ANSWER | 0.01 s | details |
| #43 | WRONG ANSWER | 0.01 s | details |
| #44 | WRONG ANSWER | 0.01 s | details |
| #45 | WRONG ANSWER | 0.01 s | details |
| #46 | WRONG ANSWER | 0.01 s | details |
| #47 | WRONG ANSWER | 0.01 s | details |
| #48 | WRONG ANSWER | 0.01 s | details |
| #49 | WRONG ANSWER | 0.01 s | details |
| #50 | WRONG ANSWER | 0.01 s | details |
| #51 | WRONG ANSWER | 0.01 s | details |
| #52 | WRONG ANSWER | 0.01 s | details |
| #53 | WRONG ANSWER | 0.01 s | details |
| #54 | WRONG ANSWER | 0.01 s | details |
| #55 | WRONG ANSWER | 0.01 s | details |
| #56 | WRONG ANSWER | 0.01 s | details |
| #57 | WRONG ANSWER | 0.01 s | details |
| #58 | WRONG ANSWER | 0.01 s | details |
| #59 | WRONG ANSWER | 0.01 s | details |
| #60 | WRONG ANSWER | 0.01 s | details |
| #61 | WRONG ANSWER | 0.13 s | details |
| #62 | WRONG ANSWER | 0.12 s | details |
| #63 | WRONG ANSWER | 0.11 s | details |
| #64 | WRONG ANSWER | 0.12 s | details |
| #65 | WRONG ANSWER | 0.16 s | details |
| #66 | WRONG ANSWER | 0.09 s | details |
| #67 | WRONG ANSWER | 0.15 s | details |
| #68 | WRONG ANSWER | 0.08 s | details |
| #69 | WRONG ANSWER | 0.14 s | details |
| #70 | WRONG ANSWER | 0.09 s | details |
Code
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e5;
vector<int> V[N];
int8_t Z[N];
vector<int> T;
ll R[N];
void topo(int i) {
if (Z[i] == 1) {
cout << "NO\n";
exit(0);
} else if (Z[i]) return;
Z[i] = 1;
for (int b : V[i]) topo(b);
Z[i] = 2;
T.push_back(i);
}
ll f(int i) {
if (R[i]) return R[i];
if (V[i].empty()) {
return 0;
}
ll n = 0;
for (int j : V[i]) {
n += f(j) + 1;
}
R[i] = n;
return R[i];
}
int main() {
int n, m;
ll x;
cin >> n >> m >> x;
for (int i = 0; i < m; ++i) {
int a, b;
cin >> a >> b;
V[a-1].push_back(b-1);
}
for (int i = 0; i < n; ++i) topo(i);
reverse(T.begin(), T.end());
for (int i = 0; i < n; ++i) {
if (f(i) + 1 > x) {
cout << "NO\n";
return 0;
}
}
cout << "YES\n";
}
Test details
Test 1
Verdict: WRONG ANSWER
| input |
|---|
| 2 1 7 1 2 |
| correct output |
|---|
| Yes |
| user output |
|---|
| YES |
Test 2
Verdict: WRONG ANSWER
| input |
|---|
| 2 1 7 2 1 |
| correct output |
|---|
| Yes |
| user output |
|---|
| YES |
Test 3
Verdict: WRONG ANSWER
| input |
|---|
| 3 3 6 2 1 2 3 1 3 |
| correct output |
|---|
| Yes |
| user output |
|---|
| YES |
Test 4
Verdict: WRONG ANSWER
| input |
|---|
| 3 2 10 2 3 2 1 |
| correct output |
|---|
| Yes |
| user output |
|---|
| YES |
Test 5
Verdict: WRONG ANSWER
| input |
|---|
| 3 3 4 3 1 3 2 1 2 |
| correct output |
|---|
| Yes |
| user output |
|---|
| YES |
Test 6
Verdict: WRONG ANSWER
| input |
|---|
| 4 5 4 4 3 4 1 2 4 1 2 ... |
| correct output |
|---|
| No |
| user output |
|---|
| NO |
Test 7
Verdict: WRONG ANSWER
| input |
|---|
| 4 4 1 3 2 3 4 1 2 2 4 |
| correct output |
|---|
| No |
| user output |
|---|
| NO |
Test 8
Verdict: WRONG ANSWER
| input |
|---|
| 4 3 8 1 2 4 1 4 3 |
| correct output |
|---|
| Yes |
| user output |
|---|
| YES |
Test 9
Verdict: WRONG ANSWER
| input |
|---|
| 4 4 7 4 3 1 2 2 4 2 1 |
| correct output |
|---|
| No |
| user output |
|---|
| NO |
Test 10
Verdict: WRONG ANSWER
| input |
|---|
| 4 5 7 2 1 2 3 1 3 1 4 ... |
| correct output |
|---|
| Yes |
| user output |
|---|
| YES |
Test 11
Verdict: WRONG ANSWER
| input |
|---|
| 5 7 2 2 5 4 3 4 1 4 5 ... |
| correct output |
|---|
| No |
| user output |
|---|
| NO |
Test 12
Verdict: WRONG ANSWER
| input |
|---|
| 5 6 2 5 3 3 4 3 2 3 1 ... |
| correct output |
|---|
| No |
| user output |
|---|
| NO |
Test 13
Verdict: WRONG ANSWER
| input |
|---|
| 5 7 10 2 4 3 2 3 5 3 1 ... |
| correct output |
|---|
| No |
| user output |
|---|
| NO |
Test 14
Verdict: WRONG ANSWER
| input |
|---|
| 5 7 6 2 3 1 5 5 2 5 1 ... |
| correct output |
|---|
| No |
| user output |
|---|
| NO |
Test 15
Verdict: WRONG ANSWER
| input |
|---|
| 5 10 8 4 1 4 3 4 2 4 5 ... |
| correct output |
|---|
| No |
| user output |
|---|
| NO |
Test 16
Verdict: WRONG ANSWER
| input |
|---|
| 5 5 7 1 4 1 3 5 3 2 1 ... |
| correct output |
|---|
| Yes |
| user output |
|---|
| YES |
Test 17
Verdict: WRONG ANSWER
| input |
|---|
| 5 10 8 1 3 1 5 1 2 1 4 ... |
| correct output |
|---|
| No |
| user output |
|---|
| NO |
Test 18
Verdict: WRONG ANSWER
| input |
|---|
| 5 4 8 1 3 2 4 2 1 3 4 |
| correct output |
|---|
| Yes |
| user output |
|---|
| YES |
Test 19
Verdict: WRONG ANSWER
| input |
|---|
| 5 10 5 2 3 4 1 1 2 1 4 ... |
| correct output |
|---|
| No |
| user output |
|---|
| NO |
Test 20
Verdict: WRONG ANSWER
| input |
|---|
| 5 4 6 2 5 2 1 5 1 5 4 |
| correct output |
|---|
| Yes |
| user output |
|---|
| YES |
Test 21
Verdict: WRONG ANSWER
| input |
|---|
| 10 29 2 10 3 10 1 10 8 10 7 ... |
| correct output |
|---|
| No |
| user output |
|---|
| NO |
Test 22
Verdict: WRONG ANSWER
| input |
|---|
| 10 24 2 8 2 8 9 8 5 8 4 ... |
| correct output |
|---|
| No |
| user output |
|---|
| NO |
Test 23
Verdict: WRONG ANSWER
| input |
|---|
| 10 25 10 10 2 10 6 10 3 2 5 ... |
| correct output |
|---|
| No |
| user output |
|---|
| NO |
Test 24
Verdict: WRONG ANSWER
| input |
|---|
| 10 29 6 10 8 10 6 10 5 8 10 ... |
| correct output |
|---|
| No |
| user output |
|---|
| NO |
Test 25
Verdict: WRONG ANSWER
| input |
|---|
| 10 44 8 10 3 10 9 10 1 10 6 ... |
| correct output |
|---|
| No |
| user output |
|---|
| NO |
Test 26
Verdict: WRONG ANSWER
| input |
|---|
| 10 17 7 3 8 6 5 6 2 9 3 ... |
| correct output |
|---|
| No |
| user output |
|---|
| NO |
Test 27
Verdict: WRONG ANSWER
| input |
|---|
| 10 42 8 9 7 9 8 9 6 9 10 ... |
| correct output |
|---|
| No |
| user output |
|---|
| NO |
Test 28
Verdict: WRONG ANSWER
| input |
|---|
| 10 11 8 5 7 9 5 7 10 7 8 ... |
| correct output |
|---|
| No |
| user output |
|---|
| NO |
Test 29
Verdict: WRONG ANSWER
| input |
|---|
| 10 41 5 9 1 9 5 9 3 9 6 ... |
| correct output |
|---|
| No |
| user output |
|---|
| NO |
Test 30
Verdict: WRONG ANSWER
| input |
|---|
| 10 9 6 3 1 3 4 3 8 1 7 ... |
| correct output |
|---|
| No |
| user output |
|---|
| NO |
Test 31
Verdict: WRONG ANSWER
| input |
|---|
| 100 484 159793364009 71 34 71 77 71 6 71 100 ... |
| correct output |
|---|
| Yes |
| user output |
|---|
| YES |
Test 32
Verdict: WRONG ANSWER
| input |
|---|
| 100 391 133876644548 80 94 80 38 80 72 80 79 ... |
| correct output |
|---|
| Yes |
| user output |
|---|
| YES |
Test 33
Verdict: WRONG ANSWER
| input |
|---|
| 100 405 903604029805 82 5 82 49 82 86 82 69 ... |
| correct output |
|---|
| No |
| user output |
|---|
| NO |
Test 34
Verdict: WRONG ANSWER
| input |
|---|
| 100 485 558765991856 50 14 50 99 50 67 50 63 ... |
| correct output |
|---|
| No |
| user output |
|---|
| NO |
Test 35
Verdict: WRONG ANSWER
| input |
|---|
| 100 777 785548293068 55 25 55 36 55 79 55 70 ... |
| correct output |
|---|
| Yes |
| user output |
|---|
| YES |
Test 36
Verdict: WRONG ANSWER
| input |
|---|
| 100 254 673064906661 52 69 52 1 52 27 62 92 ... |
| correct output |
|---|
| No |
| user output |
|---|
| NO |
Test 37
Verdict: WRONG ANSWER
| input |
|---|
| 100 725 776065552551 8 39 8 42 8 93 8 51 ... |
| correct output |
|---|
| Yes |
| user output |
|---|
| YES |
Test 38
Verdict: WRONG ANSWER
| input |
|---|
| 100 152 754385307168 25 97 25 35 25 95 77 49 ... |
| correct output |
|---|
| No |
| user output |
|---|
| NO |
Test 39
Verdict: WRONG ANSWER
| input |
|---|
| 100 712 484141188705 2 14 2 85 2 21 2 43 ... |
| correct output |
|---|
| No |
| user output |
|---|
| NO |
Test 40
Verdict: WRONG ANSWER
| input |
|---|
| 100 106 518519103960 35 52 35 65 35 1 10 90 ... |
| correct output |
|---|
| Yes |
| user output |
|---|
| YES |
Test 41
Verdict: WRONG ANSWER
| input |
|---|
| 200 968 159793364009 33 52 33 145 33 158 33 5 ... |
| correct output |
|---|
| Yes |
| user output |
|---|
| YES |
Test 42
Verdict: WRONG ANSWER
| input |
|---|
| 200 783 133876644548 191 46 191 148 191 172 191 199 ... |
| correct output |
|---|
| Yes |
| user output |
|---|
| YES |
Test 43
Verdict: WRONG ANSWER
| input |
|---|
| 200 810 903604029805 198 35 198 114 198 188 198 83 ... |
| correct output |
|---|
| No |
| user output |
|---|
| NO |
Test 44
Verdict: WRONG ANSWER
| input |
|---|
| 200 971 558765991856 15 135 15 69 15 26 15 165 ... |
| correct output |
|---|
| No |
| user output |
|---|
| NO |
Test 45
Verdict: WRONG ANSWER
| input |
|---|
| 200 1554 785548293068 2 47 2 103 2 25 2 84 ... |
| correct output |
|---|
| Yes |
| user output |
|---|
| YES |
Test 46
Verdict: WRONG ANSWER
| input |
|---|
| 200 510 673064906661 157 140 157 160 157 188 157 181 ... |
| correct output |
|---|
| No |
| user output |
|---|
| NO |
Test 47
Verdict: WRONG ANSWER
| input |
|---|
| 200 1450 776065552551 152 29 152 101 152 172 152 136 ... |
| correct output |
|---|
| Yes |
| user output |
|---|
| YES |
Test 48
Verdict: WRONG ANSWER
| input |
|---|
| 200 305 754385307168 109 147 56 74 56 7 56 15 ... |
| correct output |
|---|
| No |
| user output |
|---|
| NO |
Test 49
Verdict: WRONG ANSWER
| input |
|---|
| 200 1423 484141188705 143 29 143 176 143 14 143 76 ... |
| correct output |
|---|
| No |
| user output |
|---|
| NO |
Test 50
Verdict: WRONG ANSWER
| input |
|---|
| 200 213 518519103960 177 68 177 101 177 175 173 119 ... |
| correct output |
|---|
| Yes |
| user output |
|---|
| YES |
Test 51
Verdict: WRONG ANSWER
| input |
|---|
| 1000 4841 159793364009 576 121 576 902 576 377 576 491 ... |
| correct output |
|---|
| Yes |
| user output |
|---|
| YES |
Test 52
Verdict: WRONG ANSWER
| input |
|---|
| 1000 3918 133876644548 339 888 339 259 339 304 339 849 ... |
| correct output |
|---|
| Yes |
| user output |
|---|
| YES |
Test 53
Verdict: WRONG ANSWER
| input |
|---|
| 1000 4051 903604029805 35 303 35 119 69 585 69 445 ... |
| correct output |
|---|
| No |
| user output |
|---|
| NO |
Test 54
Verdict: WRONG ANSWER
| input |
|---|
| 1000 4855 558765991856 62 306 62 581 62 574 62 248 ... |
| correct output |
|---|
| No |
| user output |
|---|
| NO |
Test 55
Verdict: WRONG ANSWER
| input |
|---|
| 1000 7770 785548293068 884 615 884 721 884 158 884 812 ... |
| correct output |
|---|
| Yes |
| user output |
|---|
| YES |
Test 56
Verdict: WRONG ANSWER
| input |
|---|
| 1000 2553 673064906661 203 432 203 526 4 534 4 187 ... |
| correct output |
|---|
| No |
| user output |
|---|
| NO |
Test 57
Verdict: WRONG ANSWER
| input |
|---|
| 1000 7250 776065552551 39 227 39 503 39 293 39 680 ... |
| correct output |
|---|
| Yes |
| user output |
|---|
| YES |
Test 58
Verdict: WRONG ANSWER
| input |
|---|
| 1000 1533 754385307168 882 796 882 530 815 388 815 842 ... |
| correct output |
|---|
| No |
| user output |
|---|
| NO |
Test 59
Verdict: WRONG ANSWER
| input |
|---|
| 1000 7114 484141188705 32 267 32 642 32 225 32 548 ... |
| correct output |
|---|
| No |
| user output |
|---|
| NO |
Test 60
Verdict: WRONG ANSWER
| input |
|---|
| 1000 1071 518519103960 877 657 877 953 951 871 951 280 ... |
| correct output |
|---|
| Yes |
| user output |
|---|
| YES |
Test 61
Verdict: WRONG ANSWER
| input |
|---|
| 100000 154882 159793364009 52158 95830 52158 57997 10337 65466 10337 77949 ... |
| correct output |
|---|
| Yes |
| user output |
|---|
| YES |
Test 62
Verdict: WRONG ANSWER
| input |
|---|
| 100000 141702 133876644548 31918 98425 31918 27390 53839 48968 53839 65439 ... |
| correct output |
|---|
| Yes |
| user output |
|---|
| YES |
Test 63
Verdict: WRONG ANSWER
| input |
|---|
| 100000 143600 903604029805 58753 61357 58753 97879 58753 43009 77673 78316 ... |
| correct output |
|---|
| No |
| user output |
|---|
| NO |
Test 64
Verdict: WRONG ANSWER
| input |
|---|
| 100000 155080 558765991856 12714 27835 12714 87301 95755 24081 85090 72001 ... |
| correct output |
|---|
| No |
| user output |
|---|
| NO |
Test 65
Verdict: WRONG ANSWER
| input |
|---|
| 100000 196705 785548293068 64073 29701 64073 61899 64073 56663 64073 66942 ... |
| correct output |
|---|
| Yes |
| user output |
|---|
| YES |
Test 66
Verdict: WRONG ANSWER
| input |
|---|
| 100000 122199 673064906661 23466 47435 23466 38689 23466 81724 37777 76030 ... |
| correct output |
|---|
| No |
| user output |
|---|
| NO |
Test 67
Verdict: WRONG ANSWER
| input |
|---|
| 100000 189288 776065552551 56701 64161 56701 73527 56701 62864 25272 36550 ... |
| correct output |
|---|
| Yes |
| user output |
|---|
| YES |
Test 68
Verdict: WRONG ANSWER
| input |
|---|
| 100000 107630 754385307168 73409 77767 73409 20547 73409 2238 73409 7077 ... |
| correct output |
|---|
| No |
| user output |
|---|
| NO |
Test 69
Verdict: WRONG ANSWER
| input |
|---|
| 100000 187345 484141188705 66892 73373 62424 14951 73818 38984 73818 46385 ... |
| correct output |
|---|
| No |
| user output |
|---|
| NO |
Test 70
Verdict: WRONG ANSWER
| input |
|---|
| 100000 101036 518519103960 30507 31372 1379 74720 1379 56182 1379 8486 ... |
| correct output |
|---|
| Yes |
| user output |
|---|
| YES |