CSES - BAPC 2017 - Results
Submission details
Task:King of the Waves
Sender:Antti Röyskö
Submission time:2017-10-24 19:18:41 +0300
Language:C++
Status:READY
Result:ACCEPTED
Test results
testverdicttime
#1ACCEPTED0.05 sdetails
#2ACCEPTED0.04 sdetails
#3ACCEPTED0.03 sdetails
#4ACCEPTED0.04 sdetails
#5ACCEPTED0.04 sdetails
#6ACCEPTED0.08 sdetails
#7ACCEPTED0.08 sdetails
#8ACCEPTED0.09 sdetails
#9ACCEPTED0.09 sdetails
#10ACCEPTED0.10 sdetails
#11ACCEPTED0.07 sdetails
#12ACCEPTED0.07 sdetails
#13ACCEPTED0.07 sdetails
#14ACCEPTED0.09 sdetails
#15ACCEPTED0.10 sdetails
#16ACCEPTED0.10 sdetails
#17ACCEPTED0.07 sdetails
#18ACCEPTED0.07 sdetails
#19ACCEPTED0.09 sdetails
#20ACCEPTED0.09 sdetails
#21ACCEPTED0.07 sdetails
#22ACCEPTED0.11 sdetails
#23ACCEPTED0.09 sdetails
#24ACCEPTED0.08 sdetails
#25ACCEPTED0.10 sdetails
#26ACCEPTED0.09 sdetails

Compiler report

input/code.cpp: In function 'void f2(int)':
input/code.cpp:23:32: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=0; i<rt[c].size(); ++i){
                                ^

Code

#include <iostream>
#include <vector>
using namespace std;
int n;
string ss[1010];
vector<int> rt[1010];

bool u[1010];

void f(int c){
    u[c]=1;
    for (int i=0; i<n; ++i){
        if (ss[c][i]=='1'){
            if (u[i]) continue;
            rt[c].push_back(i);
            f(i);
        }
    }
}


void f2(int c){
    for (int i=0; i<rt[c].size(); ++i){
        f2(rt[c][i]);
    }
    cout << c << " ";
}


int main(){
    cin >> n;
    for (int i=0; i<n; ++i){
        cin >> ss[i];
    }
    u[0]=1;
    f(0);
    bool can=1;
    for (int i=0; i<n; ++i){
        if (!u[i]){
            can=0;
        }
    }
    if (!can){
        cout << "impossible\n";
    }else{
        f2(0);
        cout << "\n";
    }
}

Test details

Test 1

Verdict: ACCEPTED

input
5
X1111
0X111
00X11
000X1
...

correct output
4 3 2 1 0

user output
4 3 2 1 0 

Test 2

Verdict: ACCEPTED

input
8
X1000000
0X110000
10X11000
100X0110
...

correct output
7 6 5 4 3 2 1 0

user output
6 7 4 5 3 2 1 0 

Test 3

Verdict: ACCEPTED

input
4
X000
1X00
11X0
111X

correct output
impossible

user output
impossible

Test 4

Verdict: ACCEPTED

input
5
X0010
1X011
11X10
000X0
...

correct output
impossible

user output
impossible

Test 5

Verdict: ACCEPTED

input
9
X00010000
1X1011110
10X011010
111X11010
...

correct output
impossible

user output
impossible

Test 6

Verdict: ACCEPTED

input
1000
X10000000000000000000000000000...

correct output
999 998 997 996 995 994 993 99...

user output
999 998 997 996 995 994 993 99...

Test 7

Verdict: ACCEPTED

input
1000
X00000000000000000000000000000...

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

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

Test 8

Verdict: ACCEPTED

input
1000
X00000000000000000000000000000...

correct output
71 207 274 877 354 592 860 974...

user output
71 207 274 877 354 592 860 974...

Test 9

Verdict: ACCEPTED

input
1000
X11000000000000000000000000000...

correct output
999 998 997 996 995 994 993 99...

user output
500 502 504 506 507 508 510 51...

Test 10

Verdict: ACCEPTED

input
1000
X00000000000000000000000000000...

correct output
854 334 841 623 802 320 962 28...

user output
842 818 902 776 870 971 982 94...

Test 11

Verdict: ACCEPTED

input
1000
X00000001010000100010001011010...

correct output
impossible

user output
impossible

Test 12

Verdict: ACCEPTED

input
500
X01100000010010100000011100111...

correct output
impossible

user output
impossible

Test 13

Verdict: ACCEPTED

input
1000
X00010000000000000000000000001...

correct output
impossible

user output
impossible

Test 14

Verdict: ACCEPTED

input
1000
X11101101100101000100111111101...

correct output
324 186 912 855 845 802 752 72...

user output
999 995 998 996 994 997 993 99...

Test 15

Verdict: ACCEPTED

input
1000
X00000001010000000000000010101...

correct output
impossible

user output
impossible

Test 16

Verdict: ACCEPTED

input
1000
X11011000000111110111111111011...

correct output
71 826 438 431 417 971 814 483...

user output
999 998 993 995 997 996 991 99...

Test 17

Verdict: ACCEPTED

input
1000
X10111010001101010010001111011...

correct output
impossible

user output
impossible

Test 18

Verdict: ACCEPTED

input
1000
X11101001000110111011001111010...

correct output
impossible

user output
impossible

Test 19

Verdict: ACCEPTED

input
1000
X01000100010100011110111100110...

correct output
impossible

user output
impossible

Test 20

Verdict: ACCEPTED

input
1000
X01000100001100101001001001100...

correct output
112 666 875 625 213 478 435 30...

user output
995 999 997 998 996 994 992 99...

Test 21

Verdict: ACCEPTED

input
1000
X00010100101110100101111111111...

correct output
14 7 19 17 10 3 1 16 8 5 2 999...

user output
995 999 993 996 998 997 994 98...

Test 22

Verdict: ACCEPTED

input
1000
X10011111111111111111111111111...

correct output
2 3 999 998 997 996 995 994 99...

user output
996 997 998 999 995 993 994 99...

Test 23

Verdict: ACCEPTED

input
1000
X00000000000000000000000000000...

correct output
990 988 986 980 976 967 956 95...

user output
9 12 17 20 26 27 32 35 40 45 5...

Test 24

Verdict: ACCEPTED

input
998
X10111100111111100111100111111...

correct output
989 990 997 996 992 995 994 99...

user output
987 986 981 985 984 983 982 98...

Test 25

Verdict: ACCEPTED

input
998
X10111100111111100111100111111...

correct output
994 995 990 993 997 996 992 99...

user output
987 986 981 985 984 983 982 98...

Test 26

Verdict: ACCEPTED

input
998
X10111100111111100111100111111...

correct output
impossible

user output
impossible