CSES - Aalto Competitive Programming 2024 - wk6 - Mon - Results
Submission details
Task:Terrible security
Sender:fabiank
Submission time:2024-10-07 17:49:57 +0300
Language:C++ (C++20)
Status:READY
Result:
Test results
testverdicttime
#1ACCEPTED0.00 sdetails
#20.00 sdetails
#3ACCEPTED0.00 sdetails
#40.00 sdetails
#5ACCEPTED0.00 sdetails
#60.00 sdetails
#7ACCEPTED0.00 sdetails
#80.00 sdetails
#90.00 sdetails
#100.00 sdetails
#110.00 sdetails
#120.00 sdetails
#130.00 sdetails
#140.00 sdetails
#150.00 sdetails
#16ACCEPTED0.00 sdetails
#170.00 sdetails
#18ACCEPTED0.00 sdetails
#190.00 sdetails
#200.00 sdetails
#210.00 sdetails
#220.00 sdetails
#230.00 sdetails
#24ACCEPTED0.00 sdetails
#250.00 sdetails
#260.00 sdetails
#270.00 sdetails
#280.00 sdetails
#290.00 sdetails
#300.00 sdetails
#310.00 sdetails
#320.00 sdetails
#330.00 sdetails
#340.00 sdetails
#350.00 sdetails
#360.00 sdetails
#370.00 sdetails
#380.00 sdetails
#390.00 sdetails
#400.00 sdetails
#410.00 sdetails
#420.00 sdetails
#430.00 sdetails
#440.00 sdetails
#450.00 sdetails
#460.00 sdetails
#470.00 sdetails
#480.00 sdetails
#490.00 sdetails
#500.00 sdetails
#510.00 sdetails
#520.00 sdetails
#530.00 sdetails
#540.00 sdetails
#550.00 sdetails
#560.00 sdetails
#570.00 sdetails
#580.00 sdetails
#590.00 sdetails
#600.00 sdetails
#610.00 sdetails
#620.00 sdetails
#630.00 sdetails
#640.00 sdetails
#650.04 sdetails
#660.05 sdetails
#670.05 sdetails
#680.05 sdetails
#690.05 sdetails
#700.07 sdetails
#710.06 sdetails
#720.06 sdetails
#730.06 sdetails
#740.04 sdetails

Compiler report

input/code.cpp: In function 'bool topological_sort_dfs(int, std::vector<std::vector<int> >&, std::vector<short int>&, std::vector<int>&)':
input/code.cpp:102:14: warning: unused variable 'acylic' [-Wunused-variable]
  102 |         bool acylic = topological_sort_dfs(u, adj, status, result);
      |              ^~~~~~
input/code.cpp: In function 'bool topological_sort(std::vector<std::vector<int> >&, std::vector<int>&, int)':
input/code.cpp:125:18: warning: unused variable 'acyclic' [-Wunused-variable]
  125 |             bool acyclic = topological_sort_dfs(i, adj, status, result);
      |                  ^~~~~~~
input/code.cpp: In function 'int main()':
input/code.cpp:150:10: warning: unused variable 'acylic' [-Wunused-variable]
  150 |     bool acylic = topological_sort(adj, result, 1);
      |          ^~~~~~

Code

#include <bits/stdc++.h>

#define REP(i, a, b) for (int i = a; i < b; i++)

// Type Aliases for 1D and 2D vectors with initialization
#define vll(n, val) vector<long long>(n, val) // 1D vector of long longs with size n, initialized to val
#define ll long long
#define vvi(n, m, val) vector<vector<int>>(n, vector<int>(m, val))              // 2D vector of ints (n x m), initialized to val
#define vvll(n, m, val) vector<vector<long long>>(n, vector<long long>(m, val)) // 2D vector of long longs (n x m), initialized to val

using namespace std;

void print_vector(vector<int> &x)
{
    for (int v : x)
    {
        cout << v << " ";
    }
    cout << "\n";
}

void print_matrix(vector<vector<int>> &matrix)
{
    cout << "\n"
         << "----------------" << "\n";
    for (vector<int> row : matrix)
    {
        print_vector(row);
    }
    cout << "\n"
         << "----------------" << "\n";
}

int calc_max_digit(int n)
{
    int max_digit = 0;
    while (n > 0 && max_digit < 9)
    {
        int digit = n % 10;
        if (digit > max_digit)
        {
            max_digit = digit;
        }
        n /= 10;
    }
    return max_digit;
}

// edges as edge list for outgoing node as pairs (end, cost)
vector<ll> dijkstras(int start_point, vector<vector<pair<int, int>>> edges)
{
    int n = edges.size();
    vector<bool> processed(n, false);
    vector<ll> distances(n, LLONG_MAX);
    distances[start_point] = 0;
    priority_queue<pair<ll, int>> pq;
    pq.push({0, start_point});
    while (!pq.empty())
    {
        int curr = pq.top().second;
        pq.pop();
        if (processed[curr])
        {
            continue;
        }
        processed[curr] = true;
        ll distance = distances[curr];

        for (pair<int, int> edge : edges[curr])
        {

            if (distance + edge.second < distances[edge.first])
            {
                distances[edge.first] = distance + edge.second;
                pq.push({-distances[edge.first], edge.first});
            }
        }
    }
    return distances;
}

bool topological_sort_dfs(int s, vector<vector<int>> &adj, vector<short> &status, vector<int> &result)
{
    if (status[s] == 1)
    {
        // status[s] = 2;
        // result.push_back(s);
        return false;
    }
    else if (status[s] == 2)
    {
        return true;
    }
    status[s] = 1;
    // process node s
    for (auto u : adj[s])
    {
        if (u == s)
        {
            continue;
        }
        bool acylic = topological_sort_dfs(u, adj, status, result);
        // if (!acylic)
        // {
        //     return false;
        // }
    }
    status[s] = 2;
    result.push_back(s);
    // cout << "Finished " << s << "\n";
    return true;
}

bool topological_sort(vector<vector<int>> &adj, vector<int> &result, int start = 0)
{
    int n = adj.size();
    vector<short> status(n, 0);

    // cout << "Topological sort of size " << n << "\n";

    for (int i = start; i < n; i++)
    {
        if (status[i] == 0)
        {
            bool acyclic = topological_sort_dfs(i, adj, status, result);
        }
    }
    return true;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, q;
    cin >> n >> q;

    vector<vector<int>> adj(n + 1, vector<int>());

    for (int i = 0; i < n; i++)
    {
        int end;
        cin >> end;
        adj[i + 1].push_back(end);
    }

    vector<int> result;

    bool acylic = topological_sort(adj, result, 1);

    print_vector(result);

    vector<int> opens(n + 1, 0);
    for (vector<int>::reverse_iterator riter = result.rbegin();
         riter != result.rend(); ++riter)
    {
        opens[*riter] = 1;
        // cout << "In loop with value" << *riter << "\n";
        if (adj[*riter][0] != *riter)
        {
            // cout << "Computing fleeing mates for key " << *riter << "\n";
            int succ = opens[adj[*riter][0]];
            if (succ == 0)
            {
                opens[*riter] += 1;
            }
            opens[*riter] += opens[adj[*riter][0]];
        }
    }

    for (int i = 0; i < q; i++)
    {
        int key;
        cin >> key;
        cout << opens[key] << " ";
    }
    cout << endl;
}

Test details

Test 1

Verdict: ACCEPTED

input
1 1


correct output

user output


Test 2

Verdict:

input
2 2
2 1 
1 1 

correct output
2 2 

user output
2 1 
2 2 

Test 3

Verdict: ACCEPTED

input
2 1
1 2 

correct output

user output
1 2 

Test 4

Verdict:

input
3 1
2 1 3 

correct output

user output
2 1 3 

Test 5

Verdict: ACCEPTED

input
3 1
2 1 3 

correct output

user output
2 1 3 

Test 6

Verdict:

input
3 3
1 2 3 
2 3 3 

correct output
1 1 1 

user output
1 2 3 
1 1 1 

Test 7

Verdict: ACCEPTED

input
3 1
1 2 3 

correct output

user output
1 2 3 

Test 8

Verdict:

input
3 2
1 3 2 
3 1 

correct output
2 1 

user output
1 3 2 
3 1 

Test 9

Verdict:

input
4 3
1 2 4 3 
1 1 3 

correct output
1 1 2 

user output
1 2 4 3 
1 1 2 

Test 10

Verdict:

input
4 3
2 3 1 4 
1 2 2 

correct output
3 3 3 

user output
3 2 1 4 
2 2 2 

Test 11

Verdict:

input
4 3
1 2 3 4 
4 1 3 

correct output
1 1 1 

user output
1 2 3 4 
1 1 1 

Test 12

Verdict:

input
4 1
3 4 1 2 

correct output

user output
3 1 4 2 

Test 13

Verdict:

input
4 4
2 1 3 4 
3 4 1 1 

correct output
1 1 2 2 

user output
2 1 3 4 
1 1 2 2 

Test 14

Verdict:

input
4 3
2 1 3 4 
2 1 1 

correct output
2 2 2 

user output
2 1 3 4 
3 2 2 

Test 15

Verdict:

input
5 5
1 3 2 4 5 
3 5 3 4 4 

correct output
2 1 2 1 1 

user output
1 3 2 4 5 
3 1 3 1 1 

Test 16

Verdict: ACCEPTED

input
5 1
1 3 2 5 4 

correct output

user output
1 3 2 5 4 

Test 17

Verdict:

input
5 5
1 2 5 4 3 
3 3 3 2 2 

correct output
2 2 2 1 1 

user output
1 2 5 3 4 
2 2 2 1 1 

Test 18

Verdict: ACCEPTED

input
5 1
1 2 3 4 5 

correct output

user output
1 2 3 4 5 

Test 19

Verdict:

input
5 5
3 4 5 1 2 
3 1 5 5 4 

correct output
5 5 5 5 5 

user output
4 2 5 3 1 
2 2 2 2 3 

Test 20

Verdict:

input
5 2
1 4 3 5 2 
5 5 

correct output
3 3 

user output
1 5 4 2 3 
3 3 

Test 21

Verdict:

input
5 2
1 5 3 2 4 
5 1 

correct output
3 1 

user output
1 4 5 2 3 
2 1 

Test 22

Verdict:

input
5 4
1 2 3 4 5 
3 5 2 3 

correct output
1 1 1 1 

user output
1 2 3 4 5 
1 1 1 1 

Test 23

Verdict:

input
5 2
3 1 2 4 5 
5 2 

correct output
1 3 

user output
2 3 1 4 5 
1 3 

Test 24

Verdict: ACCEPTED

input
5 1
1 2 4 3 5 

correct output

user output
1 2 4 3 5 

Test 25

Verdict:

input
10 5
6 2 4 5 3 1 7 8 10 9 
7 7 4 5 3 

correct output
1 1 3 3 3 

user output
6 1 2 5 4 3 7 8 10 9 
1 1 2 3 2 

Test 26

Verdict:

input
10 10
7 2 9 4 1 5 6 10 3 8 
2 3 1 4 2 4 4 7 4 10 

correct output
1 2 4 1 1 1 1 4 1 2 

user output
5 6 7 1 2 9 3 4 10 8 
1 2 2 1 1 1 1 2 1 3 

Test 27

Verdict:

input
10 5
2 1 3 8 7 10 5 4 6 9 
4 4 2 3 7 

correct output
2 2 2 1 2 

user output
2 1 3 8 4 7 5 9 10 6 
2 2 3 1 3 

Test 28

Verdict:

input
10 9
1 7 5 4 3 2 8 6 9 10 
5 9 1 2 1 3 3 1 1 

correct output
2 1 1 4 1 2 2 1 1 

user output
1 6 8 7 2 5 3 4 9 10 
3 1 1 2 1 2 2 1 1 

Test 29

Verdict:

input
10 10
3 4 5 6 7 8 9 10 1 2 
6 2 10 9 8 7 7 6 3 2 

correct output
5 5 5 5 5 5 5 5 5 5 

user output
9 7 5 3 1 10 8 6 4 2 
2 2 3 3 2 2 2 2 2 2 

Test 30

Verdict:

input
10 5
1 4 6 5 9 7 3 8 2 10 
1 7 4 8 4 

correct output
1 3 4 1 4 

user output
1 9 5 4 2 7 6 3 8 10 
1 3 2 1 2 

Test 31

Verdict:

input
10 1
9 5 1 4 2 10 3 7 6 8 

correct output

user output
3 7 8 10 6 9 1 5 2 4 

Test 32

Verdict:

input
10 10
1 3 2 5 4 6 7 10 8 9 
4 6 3 6 1 1 5 3 1 5 

correct output
2 1 2 1 1 1 2 2 1 2 

user output
1 3 2 5 4 6 7 9 10 8 
2 1 3 1 1 1 3 3 1 3 

Test 33

Verdict:

input
10 6
8 6 3 10 1 5 7 2 4 9 
9 3 5 1 7 5 

correct output
3 1 5 5 1 5 

user output
5 6 2 8 1 3 9 10 4 7 
3 1 3 2 1 3 

Test 34

Verdict:

input
10 1
1 4 2 3 7 5 6 8 9 10 

correct output

user output
1 3 4 2 6 7 5 8 9 10 

Test 35

Verdict:

input
100 78
8 2 4 12 9 1 7 6 3 11 10 5 15 ...

correct output
11 8 3 2 1 1 1 5 8 5 1 5 6 1 4...

user output
6 8 1 2 9 5 12 4 3 7 11 10 20 ...
Truncated

Test 36

Verdict:

input
100 6
7 17 9 15 1 5 6 19 16 8 20 12 ...

correct output
3 7 3 5 10 7 

user output
5 6 7 1 14 13 17 2 16 9 3 15 4...
Truncated

Test 37

Verdict:

input
100 35
2 1 3 4 5 8 15 14 6 7 11 9 12 ...

correct output
5 12 2 2 12 13 13 12 7 12 3 12...

user output
2 1 3 4 5 9 12 13 14 8 6 10 15...
Truncated

Test 38

Verdict:

input
100 98
1 2 18 5 7 15 11 19 6 3 17 10 ...

correct output
16 7 14 11 4 11 14 14 14 16 14...

user output
1 2 10 12 17 11 7 5 4 14 19 8 ...
Truncated

Test 39

Verdict:

input
100 91
3 4 5 6 7 8 9 10 11 12 13 14 1...

correct output
50 50 50 50 50 50 50 50 50 50 ...

user output
99 97 95 93 91 89 87 85 83 81 ...
Truncated

Test 40

Verdict:

input
100 57
6 5 3 2 4 1 14 17 36 41 32 22 ...

correct output
1 2 12 2 1 7 5 10 3 10 10 29 1...

user output
6 1 4 5 2 3 14 7 37 20 21 17 8...
Truncated

Test 41

Verdict:

input
100 58
11 92 21 40 79 26 20 7 53 16 3...

correct output
18 68 68 18 68 18 18 68 68 68 ...

user output
66 50 38 21 3 20 7 8 98 91 95 ...
Truncated

Test 42

Verdict:

input
100 47
23 5 11 3 16 21 13 10 8 18 15 ...

correct output
15 15 10 10 10 10 1 5 10 10 7 ...

user output
23 1 22 12 20 21 6 15 11 3 4 1...
Truncated

Test 43

Verdict:

input
100 54
42 57 3 73 56 79 95 17 60 23 8...

correct output
72 8 72 18 72 72 18 72 1 72 72...

user output
28 25 91 30 84 49 54 20 56 5 6...
Truncated

Test 44

Verdict:

input
100 8
16 14 30 28 23 1 26 25 8 22 13...

correct output
21 3 1 1 6 21 1 4 

user output
6 37 30 3 25 8 9 16 1 35 27 32...
Truncated

Test 45

Verdict:

input
200 32
8 2 4 12 9 1 7 6 3 11 10 5 15 ...

correct output
11 1 15 15 11 5 5 8 9 11 15 3 ...

user output
6 8 1 2 9 5 12 4 3 7 11 10 20 ...
Truncated

Test 46

Verdict:

input
200 30
7 17 9 15 1 5 6 19 16 8 20 12 ...

correct output
13 1 5 2 10 4 11 4 13 11 6 4 1...

user output
5 6 7 1 14 13 17 2 16 9 3 15 4...
Truncated

Test 47

Verdict:

input
200 87
2 1 3 4 5 8 15 14 6 7 11 9 12 ...

correct output
6 6 3 14 3 12 3 2 4 2 2 9 11 1...

user output
2 1 3 4 5 9 12 13 14 8 6 10 15...
Truncated

Test 48

Verdict:

input
200 75
1 2 18 5 7 15 11 19 6 3 17 10 ...

correct output
10 8 5 7 9 9 10 7 10 7 2 1 3 1...

user output
1 2 10 12 17 11 7 5 4 14 19 8 ...
Truncated

Test 49

Verdict:

input
200 181
3 4 5 6 7 8 9 10 11 12 13 14 1...

correct output
100 100 100 100 100 100 100 10...

user output
199 197 195 193 191 189 187 18...
Truncated

Test 50

Verdict:

input
200 63
6 5 10 2 8 1 3 4 9 12 11 7 82 ...

correct output
19 22 19 39 1 19 7 39 6 4 27 3...

user output
6 1 4 8 5 2 7 12 10 3 9 11 104...
Truncated

Test 51

Verdict:

input
200 99
11 92 21 164 79 144 20 7 105 1...

correct output
138 38 138 138 138 138 138 2 1...

user output
66 50 110 200 38 186 21 3 20 7...
Truncated

Test 52

Verdict:

input
200 52
31 25 18 4 38 19 46 29 8 44 21...

correct output
57 57 13 42 24 57 15 42 57 42 ...

user output
43 15 38 5 45 18 3 22 27 12 20...
Truncated

Test 53

Verdict:

input
200 95
42 57 3 119 56 173 95 191 60 1...

correct output
144 144 144 32 144 144 144 144...

user output
28 25 91 30 84 135 127 128 49 ...
Truncated

Test 54

Verdict:

input
200 11
16 67 30 28 23 1 38 61 64 22 1...

correct output
63 16 63 47 47 12 47 3 6 47 1 

user output
6 55 42 37 30 3 71 25 61 8 73 ...
Truncated

Test 55

Verdict:

input
1000 411
8 2 4 12 9 1 7 6 3 11 10 5 15 ...

correct output
3 11 1 8 9 1 1 6 12 1 1 7 4 14...

user output
6 8 1 2 9 5 12 4 3 7 11 10 20 ...
Truncated

Test 56

Verdict:

input
1000 186
7 17 9 15 1 5 6 19 16 8 20 12 ...

correct output
13 3 2 10 17 4 12 3 1 7 9 8 11...

user output
5 6 7 1 14 13 17 2 16 9 3 15 4...
Truncated

Test 57

Verdict:

input
1000 952
2 1 3 4 5 8 15 14 6 7 11 9 12 ...

correct output
5 19 7 7 5 4 1 14 11 8 3 6 12 ...

user output
2 1 3 4 5 9 12 13 14 8 6 10 15...
Truncated

Test 58

Verdict:

input
1000 975
1 2 18 5 7 15 11 19 6 3 17 10 ...

correct output
1 5 3 4 5 6 9 8 1 15 10 15 4 2...

user output
1 2 10 12 17 11 7 5 4 14 19 8 ...
Truncated

Test 59

Verdict:

input
1000 901
3 4 5 6 7 8 9 10 11 12 13 14 1...

correct output
500 500 500 500 500 500 500 50...

user output
999 997 995 993 991 989 987 98...
Truncated

Test 60

Verdict:

input
1000 294
6 22 37 28 14 56 55 49 29 12 4...

correct output
30 231 231 290 290 290 244 2 1...

user output
16 56 6 1 24 28 4 18 30 19 49 ...
Truncated

Test 61

Verdict:

input
1000 635
446 970 21 164 995 689 783 426...

correct output
681 681 681 681 83 83 681 198 ...

user output
261 66 952 50 876 720 667 589 ...
Truncated

Test 62

Verdict:

input
1000 59
217 160 224 49 38 19 46 194 8 ...

correct output
27 52 333 333 23 333 333 27 33...

user output
153 43 193 212 144 142 54 15 1...
Truncated

Test 63

Verdict:

input
1000 981
451 340 330 827 925 173 494 19...

correct output
634 634 149 634 634 634 634 63...

user output
28 848 25 682 91 992 370 834 9...
Truncated

Test 64

Verdict:

input
1000 250
16 272 312 28 23 258 144 194 2...

correct output
186 70 88 70 186 246 70 88 246...

user output
191 151 308 258 6 336 188 215 ...
Truncated

Test 65

Verdict:

input
100000 15183
8 2 4 12 9 1 7 6 3 11 10 5 15 ...

correct output
3 2 8 9 6 4 18 7 13 8 3 6 10 1...

user output
6 8 1 2 9 5 12 4 3 7 11 10 20 ...
Truncated

Test 66

Verdict:

input
100000 80738
7 17 9 15 1 5 6 19 16 8 20 12 ...

correct output
9 2 2 2 8 8 7 4 12 9 5 4 14 6 ...

user output
5 6 7 1 14 13 17 2 16 9 3 15 4...
Truncated

Test 67

Verdict:

input
100000 88540
2 1 3 4 5 8 15 14 6 7 11 9 12 ...

correct output
4 13 2 2 3 1 15 11 4 2 12 13 1...

user output
2 1 3 4 5 9 12 13 14 8 6 10 15...
Truncated

Test 68

Verdict:

input
100000 95145
1 2 18 5 7 15 11 19 6 3 17 10 ...

correct output
12 8 5 2 1 9 13 17 5 14 1 11 5...

user output
1 2 10 12 17 11 7 5 4 14 19 8 ...
Truncated

Test 69

Verdict:

input
100000 90064
3 4 5 6 7 8 9 10 11 12 13 14 1...

correct output
50000 50000 50000 50000 50000 ...

user output
99999 99997 99995 99993 99991 ...
Truncated

Test 70

Verdict:

input
100000 98544
1197 327 641 3158 2038 1048 56...

correct output
51677 37867 37867 216 51677 51...

user output
5435 3000 3356 584 4588 2525 2...
Truncated

Test 71

Verdict:

input
100000 57490
70439 82301 64482 96766 51484 ...

correct output
11976 62820 62820 62820 2808 6...

user output
20247 67202 89259 66502 25868 ...
Truncated

Test 72

Verdict:

input
100000 72506
16265 2606 21836 8643 4486 321...

correct output
44533 16055 11222 11222 16055 ...

user output
5770 13207 10647 14006 14845 6...
Truncated

Test 73

Verdict:

input
100000 64645
47136 80135 73346 78143 9204 6...

correct output
13351 40626 40626 40626 40414 ...

user output
25130 24759 3440 60590 59594 5...
Truncated

Test 74

Verdict:

input
100000 6200
17945 16321 396 7538 19397 151...

correct output
115 13754 19010 13754 9095 137...

user output
3096 34457 30618 22244 14209 1...
Truncated