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:48:18 +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	ACCEPTED	0.00 s	details
#5	ACCEPTED	0.00 s	details
#6	ACCEPTED	0.07 s	details
#7	WRONG ANSWER	0.22 s	details
#8	WRONG ANSWER	0.24 s	details
#9	WRONG ANSWER	0.26 s	details
#10	WRONG ANSWER	0.28 s	details
#11	WRONG ANSWER	0.00 s	details
#12	WRONG ANSWER	0.00 s	details
#13	WRONG ANSWER	0.16 s	details
#14	ACCEPTED	0.00 s	details
#15	ACCEPTED	0.00 s	details
#16	WRONG ANSWER	0.27 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++)


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;
    queue<int> q;
    vector<int> distance(n*m,-1);
    q.push(start);
    visited[start] = true;
    distance[start] = 0;
    
    vector<int> parents(n*m, -1);

    while(!q.empty()) {
        int l = q.front(); q.pop();

        for(auto e: edges[l]) {
            if(visited[e]) continue;
            parents[e] = l;
            distance[e] = distance[l] + 1;
            q.push(e);
           
            visited[e] = true;
        }
    }
    int node = goal;
    path.push(node);

    if(distance[goal] == -1) {
        std::cout << "NO"<< "\n";
    } else {
        std::cout << "YES" << "\n" << distance[goal] << "\n";
        while(parents[node] != -1) {
            path.push(parents[node]);
            node = parents[node];
        }
        int a, b = path.top(); path.pop();

        while(!path.empty()) {
            a = b;
            b = path.top(); path.pop();
            int d = a-b;
            //std::cout << d << " HERE" << "\n";
            if(d == -1) {
                std::cout << "R";
            } else if(d == 1) {
                std::cout << "L";
            } else if(d > 0) {
                std::cout << "U";
            } else {
                std::cout << "D";
            }
        }
        std::cout << "\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: ACCEPTED

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

correct output
`YES 1 R` view save

user output
`YES 1 R` view save

Test 5

Verdict: ACCEPTED

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

correct output
`YES 3 RDD` view save

user output
`YES 3 RDD` 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 626 LLLUURUUDULULUULLLLLUUUULLULDL...` Truncated

Test 8

Verdict: WRONG ANSWER

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

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

user output
`YES 364 UDDDDDLDDDDDUDDDDDLLLDDDDLLDUD...` Truncated

Test 9

Verdict: WRONG ANSWER

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

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

user output
`YES 1003 LLLLLLLLLLLLLLLLLLLLLLLLLULLLL...` Truncated

Test 10

Verdict: WRONG ANSWER

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

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

user output
`YES 947 UDDDDDDDDDUDDDDDDDDDDUDDDDDDDD...` Truncated

Test 11

Verdict: WRONG ANSWER

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

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

user output
`YES 2000 DDDDDDDDDDDDDDDDDDDDDDDDDDDDDD...` Truncated

Test 12

Verdict: WRONG ANSWER

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

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

user output
`YES 2000 RRRRRRRRRRRRRRRRRRRRRRRRRRRRRR...` Truncated

Test 13

Verdict: WRONG ANSWER

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

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

user output
`YES 499998 UUUUUDUUUUUUUUUDUUUUUUUUUDUUUU...` 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 1998 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)