CSES - Datatähti 2024 loppu

CSES - Datatähti 2024 loppu - Results

Submission details
Task:	Polut
Sender:	DualRed
Submission time:	2024-01-20 16:39:24 +0200
Language:	C++ (C++20)
Status:	READY
Result:	0

Feedback
group	verdict	score
#1	RUNTIME ERROR	0
#2	RUNTIME ERROR	0
#3	RUNTIME ERROR	0

Test results
test	verdict	time	group
#1	ACCEPTED	0.00 s	1, 2, 3	details
#2	ACCEPTED	0.00 s	1, 2, 3	details
#3	ACCEPTED	0.01 s	1, 2, 3	details
#4	RUNTIME ERROR	0.79 s	1, 2, 3	details
#5	TIME LIMIT EXCEEDED	--	1, 2, 3	details
#6	RUNTIME ERROR	0.64 s	1, 2, 3	details
#7	RUNTIME ERROR	0.63 s	1, 2, 3	details
#8	RUNTIME ERROR	0.64 s	1, 2, 3	details
#9	RUNTIME ERROR	0.47 s	1, 2, 3	details
#10	RUNTIME ERROR	0.49 s	1, 2, 3	details
#11	RUNTIME ERROR	0.49 s	1, 2, 3	details
#12	RUNTIME ERROR	0.00 s	2, 3	details
#13	RUNTIME ERROR	0.00 s	2, 3	details
#14	RUNTIME ERROR	0.00 s	2, 3	details
#15	RUNTIME ERROR	0.00 s	2, 3	details
#16	RUNTIME ERROR	0.00 s	2, 3	details
#17	RUNTIME ERROR	0.00 s	2, 3	details
#18	RUNTIME ERROR	0.00 s	3	details
#19	RUNTIME ERROR	0.00 s	3	details
#20	RUNTIME ERROR	0.00 s	3	details
#21	RUNTIME ERROR	0.00 s	3	details
#22	RUNTIME ERROR	0.00 s	3	details
#23	RUNTIME ERROR	0.00 s	3	details

Compiler report

input/code.cpp: In function 'int main()':
input/code.cpp:53:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |             for(int i = 0; i < pathsRes.size(); i++){
      |                            ~~^~~~~~~~~~~~~~~~~
input/code.cpp:54:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |                 for(int j = 0; j < pathsRes[i].size(); j++){
      |                                ~~^~~~~~~~~~~~~~~~~~~~
input/code.cpp:81:51: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   81 |                     if(path2.size() + path.size() == n){
      |                        ~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~
input/code.cpp:85:42: warning: comparison of inte...

Code

#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;

const int N = 202;
vector<vector<int>> v(N), vr(N);
vector<vector<int>> pathsRes;
vector<bool> banned;
vector<int> to;

void dfs(int i, int b, vector<int>& path){
    path.push_back(i);
    if(i == b){
        pathsRes.push_back(path);
    }
    else{
        for(int j : v[i]){
            if(!banned[j]) dfs(j, b, path);
        }
    }
    path.pop_back();
}

int main(){
    int n, m;
    cin >> n >> m;
    if(n > 200) assert(false);

    for(int i = 0; i < m; i++){
        int a, b;
        cin >> a >> b;
        v[a].push_back(b);
        vr[b].push_back(a);
    }
    
    vector<int> sp, ep;
    for(int i = 1; i <= n; i++){
        if(v[i].size() == 0) ep.push_back(i);
        if(vr[i].size() == 0) sp.push_back(i);
    }
    if(sp.size() > 2 || ep.size() > 2){
        cout << "NO\n";
        return 0;
    }

    for(int p1 : sp){
        for(int p2 : ep){
            banned = vector<bool>(n+1, false);
            pathsRes.clear();
            vector<int> pp;
            dfs(p1, p2, pp);
            vector<vector<int>> paths = vector<vector<int>>(pathsRes.size());
            for(int i = 0; i < pathsRes.size(); i++){
                for(int j = 0; j < pathsRes[i].size(); j++){
                    paths[i].push_back(pathsRes[i][j]);
                }
            }

            for(auto path : paths){
                banned = vector<bool>(n+1, false);
                for(int i : path) banned[i] = true;

                vector<int> sp2, ep2;
                for(int i = 1; i <= n; i++){
                    if(banned[i]) continue;
                    bool s = true;
                    bool e = true;
                    for(int j : vr[i]) { if(!banned[j]) { s = false; break; } }
                    for(int j : v[i]) { if(!banned[j]) { e = false; break; } }
                    if(s) sp2.push_back(i);
                    if(e) ep2.push_back(i);
                }
                assert(sp2.size() >= 1 && ep2.size() >= 1);
                if(sp2.size() > 1 || ep2.size() > 1) continue;

                pathsRes.clear();
                vector<int> pp;
                dfs(sp2[0], ep2[0], pp);

                for(auto path2 : pathsRes){
                    if(path2.size() + path.size() == n){
                        // solution
                        cout << "YES\n";
                        cout << path.size() << " ";
                        for(int i = 0; i < path.size(); i++) cout << path[i] << " ";
                        cout << "\n" << path2.size() << " ";
                        for(int i = 0; i < path2.size(); i++) cout << path2[i] << " ";
                        cout << "\n";
                        return 0;
                    }
                }
            }
        }
    }
    cout << "NO\n";
}

Test details

Test 1

Group: 1, 2, 3

Verdict: ACCEPTED

input
`2 0` view save

correct output
`YES 1 2 1 1` view save

user output
`YES 1 1 1 2` view save

Test 2

Group: 1, 2, 3

Verdict: ACCEPTED

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

correct output
`YES 2 2 5 3 1 3 4` view save

user output
`YES 4 1 3 4 5 1 2` view save

Test 3

Group: 1, 2, 3

Verdict: ACCEPTED

input
`200 300 74 145 156 176 192 168 141 133 ...` view save

correct output
`YES 87 200 136 117 13 169 22 187 1...` view save

user output
`YES 113 105 9 85 138 71 35 167 64 ...` Truncated

Test 4

Group: 1, 2, 3

Verdict: RUNTIME ERROR

input
`200 500 37 119 47 10 17 31 130 28 ...` view save

correct output
`YES 90 84 70 170 117 129 17 31 186...` view save

user output
(empty)

Test 5

Group: 1, 2, 3

Verdict: TIME LIMIT EXCEEDED

input
`200 500 79 1 104 127 31 38 83 85 ...` view save

correct output
`YES 7 70 186 22 171 36 40 135 193 41 91 25 42 160 83 2 173 5...` view save

user output
(empty)

Test 6

Group: 1, 2, 3

Verdict: RUNTIME ERROR

input
`200 500 145 50 4 102 136 55 148 34 ...` view save

correct output
`YES 109 70 125 78 128 170 126 184 ...` view save

user output
(empty)

Test 7

Group: 1, 2, 3

Verdict: RUNTIME ERROR

input
`200 500 44 38 198 85 69 167 74 39 ...` view save

correct output
`NO` view save

user output
(empty)

Test 8

Group: 1, 2, 3

Verdict: RUNTIME ERROR

input
`200 500 41 93 98 4 171 72 127 166 ...` view save

correct output
`YES 88 76 116 195 197 82 42 130 46...` view save

user output
(empty)

Test 9

Group: 1, 2, 3

Verdict: RUNTIME ERROR

input
`192 494 17 148 82 57 100 152 38 102 ...` view save

correct output
`YES 154 191 183 77 3 173 83 112 15...` view save

user output
(empty)

Test 10

Group: 1, 2, 3

Verdict: RUNTIME ERROR

input
`193 497 24 110 17 193 129 117 23 186 ...` view save

correct output
`YES 24 156 123 30 189 95 34 5 96 1...` view save

user output
(empty)

Test 11

Group: 1, 2, 3

Verdict: RUNTIME ERROR

input
`194 500 57 158 23 40 31 50 189 121 ...` view save

correct output
`YES 27 168 116 136 175 180 12 89 6...` view save

user output
(empty)

Test 12

Group: 2, 3

Verdict: RUNTIME ERROR

input
`10000 15000 8243 3033 3299 579 4920 2342 2816 7811 ...` view save

correct output
`YES 9236 3099 5585 9185 7222 9342 ...` view save

user output
(empty)

Error:

code: input/code.cpp:27: int main(): Assertion `false' failed.

Test 13

Group: 2, 3

Verdict: RUNTIME ERROR

input
`10000 20000 6246 3603 5105 3531 6953 4682 2625 3510 ...` view save

correct output
`YES 8734 5847 7473 5388 4872 4557 ...` view save

user output
(empty)

Error:

code: input/code.cpp:27: int main(): Assertion `false' failed.

Test 14

Group: 2, 3

Verdict: RUNTIME ERROR

input
`10000 20000 5853 1019 2465 2936 2022 3609 9429 4118 ...` view save

correct output
`YES 5204 3987 6388 4732 4403 7869 ...` view save

user output
(empty)

Error:

code: input/code.cpp:27: int main(): Assertion `false' failed.

Test 15

Group: 2, 3

Verdict: RUNTIME ERROR

input
`10000 20000 3439 3806 9336 5210 7784 848 5162 9830 ...` view save

correct output
`NO` view save

user output
(empty)

Error:

code: input/code.cpp:27: int main(): Assertion `false' failed.

Test 16

Group: 2, 3

Verdict: RUNTIME ERROR

input
`10000 20000 8908 287 2525 6024 1851 844 72 6898 ...` view save

correct output
`YES 2487 3806 7839 4969 2661 4199 ...` view save

user output
(empty)

Error:

code: input/code.cpp:27: int main(): Assertion `false' failed.

Test 17

Group: 2, 3

Verdict: RUNTIME ERROR

input
`7621 19995 6223 473 4893 990 5326 3614 421 591 ...` view save

correct output
`YES 6340 5076 2779 1201 7053 1720 ...` view save

user output
(empty)

Error:

code: input/code.cpp:27: int main(): Assertion `false' failed.

Test 18

Group: 3

Verdict: RUNTIME ERROR

input
`200000 300000 17151 175317 68698 43101 190738 54240 105443 37722 ...` view save

correct output
`YES 163946 182154 120966 26194 771...` view save

user output
(empty)

Error:

code: input/code.cpp:27: int main(): Assertion `false' failed.

Test 19

Group: 3

Verdict: RUNTIME ERROR

input
`200000 500000 128290 197429 67543 48696 156347 40114 114481 197 ...` view save

correct output
`YES 30833 112330 10351 23335 11682...` view save

user output
(empty)

Error:

code: input/code.cpp:27: int main(): Assertion `false' failed.

Test 20

Group: 3

Verdict: RUNTIME ERROR

input
`200000 500000 93623 55553 60858 72598 15531 30650 196624 28459 ...` view save

correct output
`YES 99923 156477 12892 147937 1060...` view save

user output
(empty)

Error:

code: input/code.cpp:27: int main(): Assertion `false' failed.

Test 21

Group: 3

Verdict: RUNTIME ERROR

input
`200000 500000 76457 8199 163450 19462 107840 24269 178642 128924 ...` view save

correct output
`NO` view save

user output
(empty)

Error:

code: input/code.cpp:27: int main(): Assertion `false' failed.

Test 22

Group: 3

Verdict: RUNTIME ERROR

input
`200000 500000 181062 44502 115318 176115 33437 57568 163325 17752 ...` view save

correct output
`YES 141551 129409 52010 108449 242...` view save

user output
(empty)

Error:

code: input/code.cpp:27: int main(): Assertion `false' failed.

Test 23

Group: 3

Verdict: RUNTIME ERROR

input
`190479 499998 113031 136485 5993 50604 19834 84581 39043 93744 ...` view save

correct output
`YES 170843 113031 163271 166394 43...` view save

user output
(empty)

Error:

code: input/code.cpp:27: int main(): Assertion `false' failed.

Datatähti 2024 loppu

Polut

Compiler report

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

Tasks

Submissions (DualRed)