답안 #856951

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
856951	2023-10-05T00:58:16 Z	teesla	Tracks in the Snow (BOI13_tracks)	C++14	84.6875 / 100	2000 ms	148136 KB

tracks

#include <bits/stdc++.h>
using namespace std;
const int maxn = 4005;
typedef pair<int,int> ii;
typedef pair<int, ii> iii;

int adj[maxn][maxn], vis[maxn][maxn];
int vx[4] = {0,1,0,-1}, vy[4] = {1,0,-1,0};
int h,w;


int dijkstra(){

    priority_queue<iii, vector<iii> , greater<iii>> q;
    vis[h][w] = 1;

    q.push({1,{h,w}});
    int maior = 1;

    while(!q.empty()){

        auto [a,b] = q.top();
        auto [x,y] = b;
        q.pop();

        if(vis[x][y] < a) continue;
        maior = max(maior, a);

        for(int i=0; i<4; i++){

            int xx = x + vx[i], yy = y + vy[i];
            if(adj[xx][yy] == 0) continue;

            int val = a;

            if(adj[x][y] != adj[xx][yy]) val += 1;

            if(vis[xx][yy] != 0 and vis[xx][yy] <= val) continue;
            vis[xx][yy] = val;
            q.push({val, {xx,yy}});
        }
    }
    return maior;
}

int main(){

     cin >> h >> w;


    for(int i=1; i<=h; i++){

        string s; cin >> s;

        for(int j =0; j<w; j++){

            int val = 0;
            if(s[j] == 'R') val = 1;
            else if(s[j] == 'F') val = 2;

            adj[i][j+1] = val;
        }

    }


    cout << dijkstra() << endl;
    return 0;
}

Compilation message

tracks.cpp: In function 'int dijkstra()':
tracks.cpp:22:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   22 |         auto [a,b] = q.top();
      |              ^
tracks.cpp:23:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   23 |         auto [x,y] = b;
      |              ^

Subtask #1

30.0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	46 ms	15148 KB	Output is correct
2	Correct	1 ms	4444 KB	Output is correct
3	Correct	1 ms	4444 KB	Output is correct
4	Correct	28 ms	15132 KB	Output is correct
5	Correct	5 ms	9816 KB	Output is correct
6	Correct	1 ms	4440 KB	Output is correct
7	Correct	1 ms	4444 KB	Output is correct
8	Correct	1 ms	4444 KB	Output is correct
9	Correct	1 ms	6492 KB	Output is correct
10	Correct	7 ms	9300 KB	Output is correct
11	Correct	8 ms	9308 KB	Output is correct
12	Correct	17 ms	9932 KB	Output is correct
13	Correct	5 ms	9820 KB	Output is correct
14	Correct	5 ms	9820 KB	Output is correct
15	Correct	35 ms	14788 KB	Output is correct
16	Correct	46 ms	15444 KB	Output is correct
17	Correct	22 ms	14940 KB	Output is correct
18	Correct	28 ms	15128 KB	Output is correct

Subtask #2

54.6875 / 70.0

#	결과	실행 시간	메모리	Grader output
1	Correct	17 ms	79448 KB	Output is correct
2	Correct	126 ms	32772 KB	Output is correct
3	Correct	495 ms	105028 KB	Output is correct
4	Correct	145 ms	54100 KB	Output is correct
5	Correct	219 ms	82808 KB	Output is correct
6	Execution timed out	2033 ms	147436 KB	Time limit exceeded
7	Correct	13 ms	80020 KB	Output is correct
8	Correct	14 ms	79452 KB	Output is correct
9	Correct	5 ms	4700 KB	Output is correct
10	Correct	1 ms	2396 KB	Output is correct
11	Correct	13 ms	81324 KB	Output is correct
12	Correct	2 ms	7004 KB	Output is correct
13	Correct	121 ms	32852 KB	Output is correct
14	Correct	69 ms	23632 KB	Output is correct
15	Correct	29 ms	28248 KB	Output is correct
16	Correct	62 ms	12708 KB	Output is correct
17	Correct	307 ms	51540 KB	Output is correct
18	Correct	109 ms	58452 KB	Output is correct
19	Correct	150 ms	54232 KB	Output is correct
20	Correct	121 ms	45652 KB	Output is correct
21	Correct	298 ms	83920 KB	Output is correct
22	Correct	220 ms	83144 KB	Output is correct
23	Correct	597 ms	69536 KB	Output is correct
24	Correct	220 ms	81088 KB	Output is correct
25	Correct	536 ms	125896 KB	Output is correct
26	Correct	1323 ms	113664 KB	Output is correct
27	Execution timed out	2021 ms	127860 KB	Time limit exceeded
28	Execution timed out	2059 ms	148136 KB	Time limit exceeded
29	Execution timed out	2106 ms	138224 KB	Time limit exceeded
30	Execution timed out	2045 ms	132976 KB	Time limit exceeded
31	Execution timed out	2031 ms	103688 KB	Time limit exceeded
32	Execution timed out	2047 ms	126380 KB	Time limit exceeded