CSES - Datatähti 2025 loppu

CSES - Datatähti 2025 loppu - Results

Submission details
Task:	Suunnistus
Sender:	Vludo
Submission time:	2025-01-18 14:39:02 +0200
Language:	C++ (C++20)
Status:	READY
Result:	43

Feedback
group	verdict	score
#1	ACCEPTED	31
#2	ACCEPTED	12
#3	WRONG ANSWER	0

Test results
test	verdict	time	group
#1	WRONG ANSWER	0.00 s	3	details
#2	ACCEPTED	0.03 s	1, 2, 3	details
#3	ACCEPTED	0.02 s	1, 2, 3	details
#4	ACCEPTED	0.02 s	1, 2, 3	details
#5	ACCEPTED	0.00 s	1, 2, 3	details
#6	ACCEPTED	0.00 s	1, 2, 3	details
#7	ACCEPTED	0.06 s	2, 3	details
#8	ACCEPTED	0.06 s	2, 3	details
#9	ACCEPTED	0.02 s	2, 3	details
#10	WRONG ANSWER	0.09 s	3	details
#11	WRONG ANSWER	0.10 s	3	details
#12	ACCEPTED	0.02 s	3	details
#13	WRONG ANSWER	0.06 s	3	details
#14	ACCEPTED	0.04 s	2, 3	details
#15	WRONG ANSWER	0.01 s	3	details
#16	WRONG ANSWER	0.00 s	3	details
#17	ACCEPTED	0.02 s	2, 3	details

Compiler report

input/code.cpp: In function 'int main()':
input/code.cpp:79:9: warning: unused variable 'summa' [-Wunused-variable]
   79 |     int summa = 0;
      |         ^~~~~

Code

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
#define F first 
#define S second
#define N 505

int n, m, k;
char arr[N][N];
int vis[N][N];
vector<pair<pii, int>> v;
int kohteet[11];

void bfs(char kohde, int visiit) {
    queue<pair<pii, int>> q;
    for (auto i : v) {
        q.push(i);
    }
    v.clear();
    while (!q.empty()) {
        // if (v.size()==kohteet[kohde-'0']) break; 
        auto[paikka, x] = q.front();
        q.pop();

        // cout << kohde << ' ' << paikka.F << ' ' << paikka.S << endl;

        if (paikka.F>0 && vis[paikka.F-1][paikka.S]!=visiit) {
            vis[paikka.F-1][paikka.S] = visiit;
            char ch = arr[paikka.F-1][paikka.S];
            if (ch==kohde) {
                v.push_back({{paikka.F-1,paikka.S},x+1});
                if (kohde == '0'+k+1) return;
            }
            if (ch!='#') q.push({{paikka.F-1,paikka.S}, x+1});
        }
        if (paikka.F<n-1 && vis[paikka.F+1][paikka.S]!=visiit) {
            vis[paikka.F+1][paikka.S] = visiit;
            char ch = arr[paikka.F+1][paikka.S];
            if (ch==kohde) {
                v.push_back({{paikka.F+1,paikka.S},x+1});
                if (kohde == '0'+k+1) return;
            }
            if (ch!='#') q.push({{paikka.F+1,paikka.S}, x+1});
        }
        if (paikka.S>0 && vis[paikka.F][paikka.S-1]!=visiit) {
            vis[paikka.F][paikka.S-1] = visiit;
            char ch = arr[paikka.F][paikka.S-1];
            if (ch==kohde) {
                v.push_back({{paikka.F,paikka.S-1},x+1});
                if (kohde == '0'+k+1) return;
            }
            if (ch!='#') q.push({{paikka.F,paikka.S-1}, x+1});
        }
        if (paikka.S<m-1 && vis[paikka.F][paikka.S+1]!=visiit) {
            vis[paikka.F][paikka.S+1] = visiit;
            char ch = arr[paikka.F][paikka.S+1];
            if (ch==kohde) {
                v.push_back({{paikka.F,paikka.S+1},x+1});
                if (kohde == '0'+k+1) return;
            }
            if (ch!='#') q.push({{paikka.F,paikka.S+1}, x+1});
        }
    }
}

int main() {
    cin >> n >> m >> k;
    pii start;
    for (int i=0;i<n;++i) {
        for (int j=0;j<m;++j) {
            cin >> arr[i][j];
            if (arr[i][j]>='0' && arr[i][j]<='9') 
                kohteet[arr[i][j]-'0']++;
            else if (arr[i][j]=='E') arr[i][j] = '0'+k+1;
            else if (arr[i][j]=='S') start = {i,j};
        }
    }
    kohteet[k+1] = 1;
    int summa = 0;
    v.push_back({start, 0});
    int visI = 1;
    bfs('1', visI++);
    // for (auto i : v) cout << "{ " << i.F.F << " " << i.F.S << ": " << i.S << " }, "; 
    // cout << endl;
    for (int kohde=2;kohde<=k+1;++kohde) {
        if (v.empty()) return 0*printf("-1\n");
        bfs('0'+kohde, visI++);
        // for (auto i : v) cout << "{ " << i.F.F << " " << i.F.S << ": " << i.S << " }, "; 
        // cout << endl;
    }

    if (v.empty()) return 0*printf("-1\n");
    cout << v[0].S << endl;
}

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
`29` view save

Test 2

Group: 1, 2, 3

Verdict: ACCEPTED

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

correct output
`301` view save

user output
`301` view save

Test 3

Group: 1, 2, 3

Verdict: ACCEPTED

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

correct output
`253` view save

user output
`253` view save

Test 4

Group: 1, 2, 3

Verdict: ACCEPTED

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

correct output
`-1` view save

user output
`-1` 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: ACCEPTED

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

correct output
`3447` view save

user output
`3447` view save

Test 8

Group: 2, 3

Verdict: ACCEPTED

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

correct output
`4952` view save

user output
`4952` view save

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: WRONG ANSWER

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

correct output
`205` view save

user output
`221` view save

Test 11

Group: 3

Verdict: WRONG ANSWER

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

correct output
`157` view save

user output
`165` view save

Test 12

Group: 3

Verdict: ACCEPTED

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

correct output
`-1` view save

user output
`-1` view save

Test 13

Group: 3

Verdict: WRONG ANSWER

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

correct output
`1313` view save

user output
`1755` view save

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
`378` view save

Test 16

Group: 3

Verdict: WRONG ANSWER

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

correct output
`135` view save

user output
`177` view save

Test 17

Group: 2, 3

Verdict: ACCEPTED

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

correct output
`-1` view save

user output
`-1` view save

Datatähti 2025 loppu

Suunnistus

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

Tasks

Submissions (Vludo)