CSES - Aalto Competitive Programming 2024 - wk2 - Mon

CSES - Aalto Competitive Programming 2024 - wk2 - Mon - Results

Submission details
Task:	Abandoned warehouse
Sender:	auni
Submission time:	2024-09-09 17:04:28 +0300
Language:	C++ (C++17)
Status:	READY
Result:	WRONG ANSWER

Test results
test	verdict	time
#1	ACCEPTED	0.00 s	details
#2	ACCEPTED	0.00 s	details
#3	ACCEPTED	0.00 s	details
#4	WRONG ANSWER	0.00 s	details
#5	WRONG ANSWER	0.00 s	details
#6	ACCEPTED	0.06 s	details
#7	WRONG ANSWER	0.19 s	details
#8	WRONG ANSWER	0.21 s	details
#9	WRONG ANSWER	0.23 s	details
#10	WRONG ANSWER	0.19 s	details
#11	ACCEPTED	0.00 s	details
#12	ACCEPTED	0.00 s	details
#13	ACCEPTED	0.18 s	details
#14	ACCEPTED	0.00 s	details
#15	ACCEPTED	0.00 s	details
#16	WRONG ANSWER	0.30 s	details

Code

#include "bits/stdc++.h"

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

#define F first
#define S second
#define PB push_back
#define MP make_pair

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

bool visit(int v, vector<bool> &visited, const vector<vector<int>> &edges, int goal, stack<char> &path) {
    if(visited[v]) return false;
    if(v == goal) {
        return true;
    }
    visited[v] = true;
    for(auto e: edges[v]) {
        bool f = visit(e, visited, edges, goal, path);
        if(f) {
            
            if(e-v == 1) {
                path.push('R');
            } else if(e-v == -1) {
                path.push('L');
            } else if(e-v > 0) {
                path.push('D');
            } else {
                path.push('U');
            }
            return true;
        }
    }
    return false;
}

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

    int n, m;
    cin >> n >> m;
    // vector<int> nodes(n);
    vector<int> map(n*m);
    vector<vector<int>> edges(n*m);
    int start= 0;
    int goal = 0;

    REP(i, 0, n) {
        REP(j, 0, m) {
            char a;
            cin >> a;

            if(a == 'A') {
                start = i*m+j;
                map[i*m + j] = '.';
                if(i > 0 && map[(i-1)*m + j] == '.') {
                    edges[(i-1)*m + j].PB((i)*m + j);
                    edges[(i)*m + j].PB((i-1)*m + j);
                } 
                if(j > 0 && map[(i)*m + j - 1] == '.') {
                    edges[(i)*m + j-1].PB((i)*m + j);
                    edges[(i)*m + j].PB((i)*m + j-1);
                }
            } else if(a == 'B') {
                goal = i*m+j;
                map[i*m + j] = '.';
                if(i > 0 && map[(i-1)*m + j] == '.') {
                    edges[(i-1)*m + j].PB((i)*m + j);
                    edges[(i)*m + j].PB((i-1)*m + j);
                } 
                if(j > 0 && map[(i)*m + j - 1] == '.') {
                    edges[(i)*m + j-1].PB((i)*m + j);
                    edges[(i)*m + j].PB((i)*m + j-1);
                }
            } else if(a == '.') {
                map[i*m + j] = '.';
                if(i > 0 && map[(i-1)*m + j] == '.') {
                    edges[(i-1)*m + j].PB((i)*m + j);
                    edges[(i)*m + j].PB((i-1)*m + j);
                } 
                if(j > 0 && map[(i)*m + j - 1] == '.') {
                    edges[(i)*m + j-1].PB((i)*m + j);
                    edges[(i)*m + j].PB((i)*m + j-1);
                }
            } else {
                map[i*m + j] = '#';
            }
        }
    }

    vector<bool> visited(n*m);
    stack<char> path;

    bool found = visit(start, visited, edges, goal, path);
    if(found) {
        cout << "YES" << "\n";
        cout << (int)path.size() << "\n";
        while(!path.empty()) {
            cout << path.top();
            path.pop();
        }
        cout << "\n";
    } else {
        cout << "NO" << "\n";
    }

    return 0;
}

Test details

Test 1

Verdict: ACCEPTED

input
`10 10 ##.A###### #.##.##.## #####..### .######### ...` view save

correct output
`NO` view save

user output
`NO` view save

Test 2

Verdict: ACCEPTED

input
`10 10 B#..##.#.. #....A##.. #.....#..# .#......#. ...` view save

correct output
`NO` view save

user output
`NO` view save

Test 3

Verdict: ACCEPTED

input
`10 10 ...#..A.#. ....B...## ...#...... .......... ...` view save

correct output
`YES 3 LLD` view save

user output
`YES 3 LLD` view save

Test 4

Verdict: WRONG ANSWER

input
`10 10 .#........ .......... .......... ........#. ...` view save

correct output
`YES 1 R` view save

user output
`YES 73 UUUUUUUULLLLLDLLDRRRURRRDLLDLL...` view save

Test 5

Verdict: WRONG ANSWER

input
`10 10 .......... .......... .......... .......... ...` view save

correct output
`YES 3 RDD` view save

user output
`YES 79 UUUUULLLDRRDLLDRRDLLDRRDLLDRRR...` view save

Test 6

Verdict: ACCEPTED

input
`1000 1000 ##.###..######.#########.###.#...` view save

correct output
`NO` view save

user output
`NO` view save

Test 7

Verdict: WRONG ANSWER

input
`1000 1000 ####.#.###....#.......##.##.#....` view save

correct output
`YES 626 LLLDDRDDDDLDLDDLLLLLDDDDLLDLDL...` view save

user output
`YES 248118 UUUUUUUUUUUUUUUUUUULUUUUUUULLU...` Truncated

Test 8

Verdict: WRONG ANSWER

input
`1000 1000 ....#.##......#....#......#......` view save

correct output
`YES 364 LULULLULLLULLLLLUULLLLUUULLLLL...` view save

user output
`YES 324322 UUUUUULUUUUUUUUUUULLLUUUUURUUR...` Truncated

Test 9

Verdict: WRONG ANSWER

input
`1000 1000 .................#......#........` view save

correct output
`YES 1003 LLLLLLLLLLLLLLLLLLLLLLLLLDLLLL...` view save

user output
`YES 420235 LLULLLLUUUUUUUUUUUUUUUURUUUUUU...` Truncated

Test 10

Verdict: WRONG ANSWER

input
`1000 1000 .................................` view save

correct output
`YES 947 LLLLLLLLLLLLLLLLLLLLLLLLLLLLLL...` view save

user output
`YES 84935 UUUUUUUUUUUUUUUUUUUUUUUUUUUUUU...` Truncated

Test 11

Verdict: ACCEPTED

input
`1000 3 A#B .#. .#. .#. ...` view save

correct output
`YES 2000 DDDDDDDDDDDDDDDDDDDDDDDDDDDDDD...` view save

user output
`YES 2000 DDDDDDDDDDDDDDDDDDDDDDDDDDDDDD...` Truncated

Test 12

Verdict: ACCEPTED

input
`3 1000 A................................` view save

correct output
`YES 2000 RRRRRRRRRRRRRRRRRRRRRRRRRRRRRR...` view save

user output
`YES 2000 RRRRRRRRRRRRRRRRRRRRRRRRRRRRRR...` Truncated

Test 13

Verdict: ACCEPTED

input
`999 999 A#...#...#...#...#...#...#...#...` view save

correct output
`YES 499998 DDDDDDDDDDDDDDDDDDDDDDDDDDDDDD...` view save

user output
`YES 499998 DDDDDDDDDDDDDDDDDDDDDDDDDDDDDD...` Truncated

Test 14

Verdict: ACCEPTED

input
`1 3 A.B` view save

correct output
`YES 2 RR` view save

user output
`YES 2 RR` view save

Test 15

Verdict: ACCEPTED

input
`2 2 ## AB` view save

correct output
`YES 1 R` view save

user output
`YES 1 R` view save

Test 16

Verdict: WRONG ANSWER

input
`1000 1000 A................................` view save

correct output
`YES 1998 RRRRRRRRRRRRRRRRRRRRRRRRRRRRRR...` view save

user output
`YES 999000 RRRRRRRRRRRRRRRRRRRRRRRRRRRRRR...` Truncated

Aalto Competitive Programming 2024 - wk2 - Mon

Abandoned warehouse

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

Tasks

Submissions (auni)