Submission #101415

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
101415	2019-03-19T01:21:59 Z	SomeoneUnknown	Tracks in the Snow (BOI13_tracks)	C++14	80.3125 / 100	2000 ms	215756 KB

tracks

#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> ii;
typedef pair<int, ii> iii;

ii mii(int b, int c){
    return make_pair(b,c);
}

iii miii(int a, int b, int c){
    return make_pair(a, mii(b,c));
}

int main(){
    ios_base::sync_with_stdio(false);
    int r, c;
    cin >> r >> c;
    string m[r];
    for(int i = 0; i < r; i++){
        cin >> m[i];
        //cout << "read";
    }
    priority_queue<iii> vable;
    vable.push(miii(-1, 0, 0));
    vable.push(miii(-1, r-1, c-1));
    int most = 0;
    while(!vable.empty()){
        iii ving = vable.top();
        vable.pop();
        int y = ving.second.first;
        int x = ving.second.second;
        if(m[y][x] == '.') continue;
        int a = ving.first;
        most = max(most, -a);
        if(y != r-1){
            vable.push(miii(a-(m[y][x]!=m[y+1][x]), y+1, x));
        }
        if(x != c-1){
            vable.push(miii(a-(m[y][x]!=m[y][x+1]), y, x+1));
        }
        if(y != 0){
            vable.push(miii(a-(m[y][x]!=m[y-1][x]), y-1, x));
        }
        if(x != 0){
            vable.push(miii(a-(m[y][x]!=m[y][x-1]), y, x-1));
        }
        m[y][x] = '.';
    }
    cout << most;//*/
}
/*
5 8
FFRF....
.FRRR...
.FFFFF..
..RRRFFR
.....FFF
*/

Subtask #1

30.0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	177 ms	1536 KB	Output is correct
2	Correct	2 ms	384 KB	Output is correct
3	Correct	3 ms	384 KB	Output is correct
4	Correct	122 ms	3696 KB	Output is correct
5	Correct	13 ms	508 KB	Output is correct
6	Correct	2 ms	384 KB	Output is correct
7	Correct	3 ms	384 KB	Output is correct
8	Correct	6 ms	512 KB	Output is correct
9	Correct	2 ms	384 KB	Output is correct
10	Correct	21 ms	640 KB	Output is correct
11	Correct	32 ms	1276 KB	Output is correct
12	Correct	62 ms	960 KB	Output is correct
13	Correct	13 ms	512 KB	Output is correct
14	Correct	14 ms	512 KB	Output is correct
15	Correct	131 ms	1228 KB	Output is correct
16	Correct	185 ms	1536 KB	Output is correct
17	Correct	77 ms	896 KB	Output is correct
18	Correct	127 ms	3692 KB	Output is correct

Subtask #2

50.3125 / 70.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	640 KB	Output is correct
2	Correct	476 ms	2368 KB	Output is correct
3	Correct	1433 ms	18620 KB	Output is correct
4	Correct	427 ms	4676 KB	Output is correct
5	Correct	628 ms	10432 KB	Output is correct
6	Execution timed out	2061 ms	215320 KB	Time limit exceeded
7	Correct	7 ms	640 KB	Output is correct
8	Correct	6 ms	768 KB	Output is correct
9	Correct	18 ms	964 KB	Output is correct
10	Correct	5 ms	544 KB	Output is correct
11	Correct	6 ms	640 KB	Output is correct
12	Correct	4 ms	384 KB	Output is correct
13	Correct	432 ms	2696 KB	Output is correct
14	Correct	229 ms	2048 KB	Output is correct
15	Correct	73 ms	1924 KB	Output is correct
16	Correct	215 ms	1860 KB	Output is correct
17	Correct	1112 ms	5572 KB	Output is correct
18	Correct	219 ms	5248 KB	Output is correct
19	Correct	360 ms	4992 KB	Output is correct
20	Correct	392 ms	4608 KB	Output is correct
21	Correct	834 ms	11008 KB	Output is correct
22	Correct	567 ms	10692 KB	Output is correct
23	Execution timed out	2057 ms	9664 KB	Time limit exceeded
24	Correct	570 ms	10756 KB	Output is correct
25	Correct	926 ms	18680 KB	Output is correct
26	Execution timed out	2073 ms	211368 KB	Time limit exceeded
27	Execution timed out	2073 ms	215756 KB	Time limit exceeded
28	Execution timed out	2058 ms	215704 KB	Time limit exceeded
29	Execution timed out	2064 ms	215704 KB	Time limit exceeded
30	Execution timed out	2045 ms	215300 KB	Time limit exceeded
31	Execution timed out	2039 ms	18112 KB	Time limit exceeded
32	Execution timed out	2060 ms	215680 KB	Time limit exceeded