CSES - Aalto Competitive Programming 2024 - wk6 - Wed

CSES - Aalto Competitive Programming 2024 - wk6 - Wed - Results

Submission details
Task:	Microservice hell
Sender:	aalto2024g_002
Submission time:	2024-10-09 16:33:28 +0300
Language:	C++ (C++11)
Status:	READY
Result:	ACCEPTED

Test results
test	verdict	time
#1	ACCEPTED	0.01 s	details
#2	ACCEPTED	0.01 s	details
#3	ACCEPTED	0.01 s	details
#4	ACCEPTED	0.01 s	details
#5	ACCEPTED	0.01 s	details
#6	ACCEPTED	0.01 s	details
#7	ACCEPTED	0.01 s	details
#8	ACCEPTED	0.01 s	details
#9	ACCEPTED	0.01 s	details
#10	ACCEPTED	0.01 s	details
#11	ACCEPTED	0.01 s	details
#12	ACCEPTED	0.01 s	details
#13	ACCEPTED	0.01 s	details
#14	ACCEPTED	0.01 s	details
#15	ACCEPTED	0.01 s	details
#16	ACCEPTED	0.01 s	details
#17	ACCEPTED	0.01 s	details
#18	ACCEPTED	0.01 s	details
#19	ACCEPTED	0.01 s	details
#20	ACCEPTED	0.01 s	details
#21	ACCEPTED	0.01 s	details
#22	ACCEPTED	0.01 s	details
#23	ACCEPTED	0.01 s	details
#24	ACCEPTED	0.01 s	details
#25	ACCEPTED	0.01 s	details
#26	ACCEPTED	0.01 s	details
#27	ACCEPTED	0.01 s	details
#28	ACCEPTED	0.01 s	details
#29	ACCEPTED	0.01 s	details
#30	ACCEPTED	0.01 s	details
#31	ACCEPTED	0.01 s	details
#32	ACCEPTED	0.01 s	details
#33	ACCEPTED	0.01 s	details
#34	ACCEPTED	0.01 s	details
#35	ACCEPTED	0.01 s	details
#36	ACCEPTED	0.01 s	details
#37	ACCEPTED	0.01 s	details
#38	ACCEPTED	0.01 s	details
#39	ACCEPTED	0.01 s	details
#40	ACCEPTED	0.01 s	details
#41	ACCEPTED	0.01 s	details
#42	ACCEPTED	0.01 s	details
#43	ACCEPTED	0.01 s	details
#44	ACCEPTED	0.01 s	details
#45	ACCEPTED	0.01 s	details
#46	ACCEPTED	0.01 s	details
#47	ACCEPTED	0.01 s	details
#48	ACCEPTED	0.01 s	details
#49	ACCEPTED	0.01 s	details
#50	ACCEPTED	0.01 s	details
#51	ACCEPTED	0.01 s	details
#52	ACCEPTED	0.01 s	details
#53	ACCEPTED	0.01 s	details
#54	ACCEPTED	0.01 s	details
#55	ACCEPTED	0.01 s	details
#56	ACCEPTED	0.01 s	details
#57	ACCEPTED	0.01 s	details
#58	ACCEPTED	0.01 s	details
#59	ACCEPTED	0.01 s	details
#60	ACCEPTED	0.01 s	details
#61	ACCEPTED	0.13 s	details
#62	ACCEPTED	0.12 s	details
#63	ACCEPTED	0.11 s	details
#64	ACCEPTED	0.12 s	details
#65	ACCEPTED	0.16 s	details
#66	ACCEPTED	0.09 s	details
#67	ACCEPTED	0.16 s	details
#68	ACCEPTED	0.09 s	details
#69	ACCEPTED	0.14 s	details
#70	ACCEPTED	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(T[i]) + 1 > x) {
      cout << "No\n";
      return 0;
    }
  }
  cout << "Yes\n";
}

Test details

Test 1

Verdict: ACCEPTED

input
`2 1 7 1 2` view save

correct output
`Yes` view save

user output
`Yes` view save

Test 2

Verdict: ACCEPTED

input
`2 1 7 2 1` view save

correct output
`Yes` view save

user output
`Yes` view save

Test 3

Verdict: ACCEPTED

input
`3 3 6 2 1 2 3 1 3` view save

correct output
`Yes` view save

user output
`Yes` view save

Test 4

Verdict: ACCEPTED

input
`3 2 10 2 3 2 1` view save

correct output
`Yes` view save

user output
`Yes` view save

Test 5

Verdict: ACCEPTED

input
`3 3 4 3 1 3 2 1 2` view save

correct output
`Yes` view save

user output
`Yes` view save

Test 6

Verdict: ACCEPTED

input
`4 5 4 4 3 4 1 2 4 1 2 ...` view save

correct output
`No` view save

user output
`No` view save

Test 7

Verdict: ACCEPTED

input
`4 4 1 3 2 3 4 1 2 2 4` view save

correct output
`No` view save

user output
`No` view save

Test 8

Verdict: ACCEPTED

input
`4 3 8 1 2 4 1 4 3` view save

correct output
`Yes` view save

user output
`Yes` view save

Test 9

Verdict: ACCEPTED

input
`4 4 7 4 3 1 2 2 4 2 1` view save

correct output
`No` view save

user output
`No` view save

Test 10

Verdict: ACCEPTED

input
`4 5 7 2 1 2 3 1 3 1 4 ...` view save

correct output
`Yes` view save

user output
`Yes` view save

Test 11

Verdict: ACCEPTED

input
`5 7 2 2 5 4 3 4 1 4 5 ...` view save

correct output
`No` view save

user output
`No` view save

Test 12

Verdict: ACCEPTED

input
`5 6 2 5 3 3 4 3 2 3 1 ...` view save

correct output
`No` view save

user output
`No` view save

Test 13

Verdict: ACCEPTED

input
`5 7 10 2 4 3 2 3 5 3 1 ...` view save

correct output
`No` view save

user output
`No` view save

Test 14

Verdict: ACCEPTED

input
`5 7 6 2 3 1 5 5 2 5 1 ...` view save

correct output
`No` view save

user output
`No` view save

Test 15

Verdict: ACCEPTED

input
`5 10 8 4 1 4 3 4 2 4 5 ...` view save

correct output
`No` view save

user output
`No` view save

Test 16

Verdict: ACCEPTED

input
`5 5 7 1 4 1 3 5 3 2 1 ...` view save

correct output
`Yes` view save

user output
`Yes` view save

Test 17

Verdict: ACCEPTED

input
`5 10 8 1 3 1 5 1 2 1 4 ...` view save

correct output
`No` view save

user output
`No` view save

Test 18

Verdict: ACCEPTED

input
`5 4 8 1 3 2 4 2 1 3 4` view save

correct output
`Yes` view save

user output
`Yes` view save

Test 19

Verdict: ACCEPTED

input
`5 10 5 2 3 4 1 1 2 1 4 ...` view save

correct output
`No` view save

user output
`No` view save

Test 20

Verdict: ACCEPTED

input
`5 4 6 2 5 2 1 5 1 5 4` view save

correct output
`Yes` view save

user output
`Yes` view save

Test 21

Verdict: ACCEPTED

input
`10 29 2 10 3 10 1 10 8 10 7 ...` view save

correct output
`No` view save

user output
`No` view save

Test 22

Verdict: ACCEPTED

input
`10 24 2 8 2 8 9 8 5 8 4 ...` view save

correct output
`No` view save

user output
`No` view save

Test 23

Verdict: ACCEPTED

input
`10 25 10 10 2 10 6 10 3 2 5 ...` view save

correct output
`No` view save

user output
`No` view save

Test 24

Verdict: ACCEPTED

input
`10 29 6 10 8 10 6 10 5 8 10 ...` view save

correct output
`No` view save

user output
`No` view save

Test 25

Verdict: ACCEPTED

input
`10 44 8 10 3 10 9 10 1 10 6 ...` view save

correct output
`No` view save

user output
`No` view save

Test 26

Verdict: ACCEPTED

input
`10 17 7 3 8 6 5 6 2 9 3 ...` view save

correct output
`No` view save

user output
`No` view save

Test 27

Verdict: ACCEPTED

input
`10 42 8 9 7 9 8 9 6 9 10 ...` view save

correct output
`No` view save

user output
`No` view save

Test 28

Verdict: ACCEPTED

input
`10 11 8 5 7 9 5 7 10 7 8 ...` view save

correct output
`No` view save

user output
`No` view save

Test 29

Verdict: ACCEPTED

input
`10 41 5 9 1 9 5 9 3 9 6 ...` view save

correct output
`No` view save

user output
`No` view save

Test 30

Verdict: ACCEPTED

input
`10 9 6 3 1 3 4 3 8 1 7 ...` view save

correct output
`No` view save

user output
`No` view save

Test 31

Verdict: ACCEPTED

input
`100 484 159793364009 71 34 71 77 71 6 71 100 ...` view save

correct output
`Yes` view save

user output
`Yes` view save

Test 32

Verdict: ACCEPTED

input
`100 391 133876644548 80 94 80 38 80 72 80 79 ...` view save

correct output
`Yes` view save

user output
`Yes` view save

Test 33

Verdict: ACCEPTED

input
`100 405 903604029805 82 5 82 49 82 86 82 69 ...` view save

correct output
`No` view save

user output
`No` view save

Test 34

Verdict: ACCEPTED

input
`100 485 558765991856 50 14 50 99 50 67 50 63 ...` view save

correct output
`No` view save

user output
`No` view save

Test 35

Verdict: ACCEPTED

input
`100 777 785548293068 55 25 55 36 55 79 55 70 ...` view save

correct output
`Yes` view save

user output
`Yes` view save

Test 36

Verdict: ACCEPTED

input
`100 254 673064906661 52 69 52 1 52 27 62 92 ...` view save

correct output
`No` view save

user output
`No` view save

Test 37

Verdict: ACCEPTED

input
`100 725 776065552551 8 39 8 42 8 93 8 51 ...` view save

correct output
`Yes` view save

user output
`Yes` view save

Test 38

Verdict: ACCEPTED

input
`100 152 754385307168 25 97 25 35 25 95 77 49 ...` view save

correct output
`No` view save

user output
`No` view save

Test 39

Verdict: ACCEPTED

input
`100 712 484141188705 2 14 2 85 2 21 2 43 ...` view save

correct output
`No` view save

user output
`No` view save

Test 40

Verdict: ACCEPTED

input
`100 106 518519103960 35 52 35 65 35 1 10 90 ...` view save

correct output
`Yes` view save

user output
`Yes` view save

Test 41

Verdict: ACCEPTED

input
`200 968 159793364009 33 52 33 145 33 158 33 5 ...` view save

correct output
`Yes` view save

user output
`Yes` view save

Test 42

Verdict: ACCEPTED

input
`200 783 133876644548 191 46 191 148 191 172 191 199 ...` view save

correct output
`Yes` view save

user output
`Yes` view save

Test 43

Verdict: ACCEPTED

input
`200 810 903604029805 198 35 198 114 198 188 198 83 ...` view save

correct output
`No` view save

user output
`No` view save

Test 44

Verdict: ACCEPTED

input
`200 971 558765991856 15 135 15 69 15 26 15 165 ...` view save

correct output
`No` view save

user output
`No` view save

Test 45

Verdict: ACCEPTED

input
`200 1554 785548293068 2 47 2 103 2 25 2 84 ...` view save

correct output
`Yes` view save

user output
`Yes` view save

Test 46

Verdict: ACCEPTED

input
`200 510 673064906661 157 140 157 160 157 188 157 181 ...` view save

correct output
`No` view save

user output
`No` view save

Test 47

Verdict: ACCEPTED

input
`200 1450 776065552551 152 29 152 101 152 172 152 136 ...` view save

correct output
`Yes` view save

user output
`Yes` view save

Test 48

Verdict: ACCEPTED

input
`200 305 754385307168 109 147 56 74 56 7 56 15 ...` view save

correct output
`No` view save

user output
`No` view save

Test 49

Verdict: ACCEPTED

input
`200 1423 484141188705 143 29 143 176 143 14 143 76 ...` view save

correct output
`No` view save

user output
`No` view save

Test 50

Verdict: ACCEPTED

input
`200 213 518519103960 177 68 177 101 177 175 173 119 ...` view save

correct output
`Yes` view save

user output
`Yes` view save

Test 51

Verdict: ACCEPTED

input
`1000 4841 159793364009 576 121 576 902 576 377 576 491 ...` view save

correct output
`Yes` view save

user output
`Yes` view save

Test 52

Verdict: ACCEPTED

input
`1000 3918 133876644548 339 888 339 259 339 304 339 849 ...` view save

correct output
`Yes` view save

user output
`Yes` view save

Test 53

Verdict: ACCEPTED

input
`1000 4051 903604029805 35 303 35 119 69 585 69 445 ...` view save

correct output
`No` view save

user output
`No` view save

Test 54

Verdict: ACCEPTED

input
`1000 4855 558765991856 62 306 62 581 62 574 62 248 ...` view save

correct output
`No` view save

user output
`No` view save

Test 55

Verdict: ACCEPTED

input
`1000 7770 785548293068 884 615 884 721 884 158 884 812 ...` view save

correct output
`Yes` view save

user output
`Yes` view save

Test 56

Verdict: ACCEPTED

input
`1000 2553 673064906661 203 432 203 526 4 534 4 187 ...` view save

correct output
`No` view save

user output
`No` view save

Test 57

Verdict: ACCEPTED

input
`1000 7250 776065552551 39 227 39 503 39 293 39 680 ...` view save

correct output
`Yes` view save

user output
`Yes` view save

Test 58

Verdict: ACCEPTED

input
`1000 1533 754385307168 882 796 882 530 815 388 815 842 ...` view save

correct output
`No` view save

user output
`No` view save

Test 59

Verdict: ACCEPTED

input
`1000 7114 484141188705 32 267 32 642 32 225 32 548 ...` view save

correct output
`No` view save

user output
`No` view save

Test 60

Verdict: ACCEPTED

input
`1000 1071 518519103960 877 657 877 953 951 871 951 280 ...` view save

correct output
`Yes` view save

user output
`Yes` view save

Test 61

Verdict: ACCEPTED

input
`100000 154882 159793364009 52158 95830 52158 57997 10337 65466 10337 77949 ...` view save

correct output
`Yes` view save

user output
`Yes` view save

Test 62

Verdict: ACCEPTED

input
`100000 141702 133876644548 31918 98425 31918 27390 53839 48968 53839 65439 ...` view save

correct output
`Yes` view save

user output
`Yes` view save

Test 63

Verdict: ACCEPTED

input
`100000 143600 903604029805 58753 61357 58753 97879 58753 43009 77673 78316 ...` view save

correct output
`No` view save

user output
`No` view save

Test 64

Verdict: ACCEPTED

input
`100000 155080 558765991856 12714 27835 12714 87301 95755 24081 85090 72001 ...` view save

correct output
`No` view save

user output
`No` view save

Test 65

Verdict: ACCEPTED

input
`100000 196705 785548293068 64073 29701 64073 61899 64073 56663 64073 66942 ...` view save

correct output
`Yes` view save

user output
`Yes` view save

Test 66

Verdict: ACCEPTED

input
`100000 122199 673064906661 23466 47435 23466 38689 23466 81724 37777 76030 ...` view save

correct output
`No` view save

user output
`No` view save

Test 67

Verdict: ACCEPTED

input
`100000 189288 776065552551 56701 64161 56701 73527 56701 62864 25272 36550 ...` view save

correct output
`Yes` view save

user output
`Yes` view save

Test 68

Verdict: ACCEPTED

input
`100000 107630 754385307168 73409 77767 73409 20547 73409 2238 73409 7077 ...` view save

correct output
`No` view save

user output
`No` view save

Test 69

Verdict: ACCEPTED

input
`100000 187345 484141188705 66892 73373 62424 14951 73818 38984 73818 46385 ...` view save

correct output
`No` view save

user output
`No` view save

Test 70

Verdict: ACCEPTED

input
`100000 101036 518519103960 30507 31372 1379 74720 1379 56182 1379 8486 ...` view save

correct output
`Yes` view save

user output
`Yes` view save

Aalto Competitive Programming 2024 - wk6 - Wed

Microservice hell

Code

Test details

Test 1

Test 2

Test 3

Test 4

Test 5

Test 6

Test 7

Test 8

Test 9

Test 10

Test 11

Test 12

Test 13

Test 14

Test 15

Test 16

Test 17

Test 18

Test 19

Test 20

Test 21

Test 22

Test 23

Test 24

Test 25

Test 26

Test 27

Test 28

Test 29

Test 30

Test 31

Test 32

Test 33

Test 34

Test 35

Test 36

Test 37

Test 38

Test 39

Test 40

Test 41

Test 42

Test 43

Test 44

Test 45

Test 46

Test 47

Test 48

Test 49

Test 50

Test 51

Test 52

Test 53

Test 54

Test 55

Test 56

Test 57

Test 58

Test 59

Test 60

Test 61

Test 62

Test 63

Test 64

Test 65

Test 66

Test 67

Test 68

Test 69

Test 70

Tasks

Submissions (aalto2024g_002)