CSES - Datatähti 2025 loppu

Submission details
Task:	Suunnistus
Sender:	Hattless
Submission time:	2025-01-18 16:40:05 +0200
Language:	C++ (C++20)
Status:	READY
Result:	0

Feedback
group	verdict	score
#1	TIME LIMIT EXCEEDED	0
#2	TIME LIMIT EXCEEDED	0
#3	WRONG ANSWER	0

Test results
test	verdict	time	group
#1	WRONG ANSWER	0.28 s	3	details
#2	TIME LIMIT EXCEEDED	--	1, 2, 3	details
#3	TIME LIMIT EXCEEDED	--	1, 2, 3	details
#4	WRONG ANSWER	0.01 s	1, 2, 3	details
#5	ACCEPTED	0.00 s	1, 2, 3	details
#6	ACCEPTED	0.00 s	1, 2, 3	details
#7	TIME LIMIT EXCEEDED	--	2, 3	details
#8	TIME LIMIT EXCEEDED	--	2, 3	details
#9	ACCEPTED	0.01 s	2, 3	details
#10	TIME LIMIT EXCEEDED	--	3	details
#11	TIME LIMIT EXCEEDED	--	3	details
#12	WRONG ANSWER	0.02 s	3	details
#13	TIME LIMIT EXCEEDED	--	3	details
#14	ACCEPTED	0.04 s	2, 3	details
#15	WRONG ANSWER	0.00 s	3	details
#16	WRONG ANSWER	0.00 s	3	details
#17	TIME LIMIT EXCEEDED	--	2, 3	details

Code

#include <bits/stdc++.h>
#define ln "\n";
using namespace std;
using ll = long long;
int n,m,k;
vector<string> vec;
vector<vector<ll>> dp;
vector<vector<pair<int,int>>> flags;
vector<vector<bool>> seen;
void bfs(int currY, int currX, char tar,int flag) {
    queue<pair<int,pair<int,ll>>> q;
    if(flag == -1) {
        q.push({currY,{currX,0}});
    } else {
        for(auto [yy,xx]:flags[flag]) {
            ll d = dp[yy][xx];
            q.push({yy,{xx,d}});
        }
    }
    seen.assign(n,vector<bool> (m,false));
    dp.assign(n,vector<ll> (m,1e9));
    while(!q.empty()) {
        int x = q.front().second.first;
        int y = q.front().first;
        ll d = q.front().second.second;
        q.pop();
        if(vec[y][x] == tar) {
            // cout << last << " " << depth << " " << currY << " " << currX << ln;
            dp[y][x] = min(d,dp[y][x]); 
            if(tar != 'E')  {
                flags[tar-'1'].push_back({y,x});
            }
        }
        // if(y == 1 && x == 1) cout << "RAN " <<  << ln;
        seen[y][x] = true;
        if(x+1 < m && vec[y][x+1] != '#' && seen[y][x+1]== false) q.push({y,{x+1,d+1}});
        if(x-1 >= 0 && vec[y][x-1] != '#' && seen[y][x-1]== false)q.push({y,{x-1,d+1}});
        if(y+1 < n && vec[y+1][x] != '#' && seen[y+1][x]== false) q.push({y+1,{x,d+1}});
        if(y-1 >= 0 && vec[y-1][x] != '#' && seen[y-1][x]== false) q.push({y-1,{x,d+1}});
    }
}

int main() {
    // ios::sync_with_stdio(0);
    // cin.tie(0);
    cin >> n >> m >> k;
    vec.resize(n);
    dp.assign(n,vector<ll> (m,1e9));
    for(int i =  0; i < n; i++) cin >> vec[i];
    seen.assign(n,vector<bool> (m,false));
    flags.resize(10);
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            if(vec[i][j] == 'S') {
                if(k == 0) {
                    bfs(i,j,'E',-1);
                } else {
                    bfs(i,j,'1',-1);
                }
                break;
            }
        }
    }
    ll mn = 1e9;
    if(k == 0) {

        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m ;j++) {
                mn = min(mn,dp[i][j]);
            }
        }
        cout << mn << ln;
        return 0;
    }
    for(int i = 2; i <= k; i++) {

        if(flags[i-2].size() == 0) {
            cout << "-1" << ln;
            return 0;
        } else {
            bfs(0,0,i+'0',i-2);
            // cout << i << ln;
            // cout << flags[1].size() << ln;
            // for(auto [y,x]:flags[i-1]) {
            //     cout << y << " " << x << " " << dp[y][x] << ln;
            // }
            // cout << ln;
        }
    }
    if(flags[k-2].size() == 0) {
        cout << "-1" << ln;
        return 0;
    } else {
        bfs(0,0,'E',k-1);
        // cout << flags[1].size() << ln;
        // // for(auto [y,x]:flags[i-1]) {
        // //     cout << y << " " << x << " " << dp[y][x] << ln;
        // // }
        // cout << ln;
    }
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m ;j++) {
            mn = min(mn,dp[i][j]);
        }
    }
    cout << mn << ln;

}

Test details

Test 1

Group: 3

Verdict: WRONG ANSWER

input
`10 10 9 S293#35616 #662963731 54975451#7 5162589168 ...` view save

correct output
`25` view save

user output
`27` view save

Test 2

Group: 1, 2, 3

Verdict: TIME LIMIT EXCEEDED

input
`500 500 0 .................................` view save

correct output
`301` view save

user output
(empty)

Test 3

Group: 1, 2, 3

Verdict: TIME LIMIT EXCEEDED

input
`500 500 0 .#.........#.#..##..#............` view save

correct output
`253` view save

user output
(empty)

Test 4

Group: 1, 2, 3

Verdict: WRONG ANSWER

input
`500 500 0 ...#......##.##.#.#..##..#..##...` view save

correct output
`-1` view save

user output
`1000000000` view save

Test 5

Group: 1, 2, 3

Verdict: ACCEPTED

input
`500 1 0 . . . . ...` view save

correct output
`77` view save

user output
`77` view save

Test 6

Group: 1, 2, 3

Verdict: ACCEPTED

input
`1 500 0 .................................` view save

correct output
`166` view save

user output
`166` view save

Test 7

Group: 2, 3

Verdict: TIME LIMIT EXCEEDED

input
`500 500 9 .................................` view save

correct output
`3447` view save

user output
(empty)

Test 8

Group: 2, 3

Verdict: TIME LIMIT EXCEEDED

input
`500 500 9 .#........#..................#...` view save

correct output
`4952` view save

user output
(empty)

Test 9

Group: 2, 3

Verdict: ACCEPTED

input
`500 500 9 ##.########.##########.#..#......` view save

correct output
`-1` view save

user output
`-1` view save

Test 10

Group: 3

Verdict: TIME LIMIT EXCEEDED

input
`500 500 9 623475428948841896621266296765...` view save

correct output
`205` view save

user output
(empty)

Test 11

Group: 3

Verdict: TIME LIMIT EXCEEDED

input
`500 500 9 7##814125813#3463#272134469457...` view save

correct output
`157` view save

user output
(empty)

Test 12

Group: 3

Verdict: WRONG ANSWER

input
`500 500 9 ##67##36##5#3###67###8972#61##...` view save

correct output
`-1` view save

user output
`1000000000` view save

Test 13

Group: 3

Verdict: TIME LIMIT EXCEEDED

input
`500 500 9 ....................#...#........` view save

correct output
`1313` view save

user output
(empty)

Test 14

Group: 2, 3

Verdict: ACCEPTED

input
`499 499 9 S#...#...#...#...#...#...#...#...` view save

correct output
`1124942` view save

user output
`1124942` view save

Test 15

Group: 3

Verdict: WRONG ANSWER

input
`500 1 9 1 6 1 3 ...` view save

correct output
`332` view save

user output
`336` view save

Test 16

Group: 3

Verdict: WRONG ANSWER

input
`1 500 9 996327784392827829434482995353...` view save

correct output
`135` view save

user output
`153` view save

Test 17

Group: 2, 3

Verdict: TIME LIMIT EXCEEDED

input
`500 500 9 .................................` view save

correct output
`-1` view save

user output
(empty)

Datatähti 2025 loppu

Suunnistus

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

Tasks

Submissions (Hattless)