Submission #101426

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
101426	2019-03-19T01:44:01 Z	dwsc	Tracks in the Snow (BOI13_tracks)	C++14	82.5 / 100	2000 ms	91336 KB

tracks

#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> ii;
typedef pair<int,ii> i3;
int main(){
    int h,w;
    cin >> h >> w;
    char grid[h][w];
    int visit[h][w];
    for (int i = 0; i < h; i++){
        for (int j = 0; j < w; j++) {
            cin >> grid[i][j];
            visit[i][j] = 0;
        }
    }
    priority_queue<i3,vector<i3>,greater<i3> > pq;
    int dx[] = {1,0,-1,0},dy[] = {0,1,0,-1};
    int ans = 1;
    visit[0][0] = 1;
    pq.push(i3(1,ii(0,0)));
    while (!pq.empty()){
        i3 f = pq.top();
        pq.pop();
        int num = f.first,x = f.second.first,y = f.second.second;
        for (int i = 0; i < 4; i++){
            int nx = x+dx[i],ny = y+dy[i];
            if (nx < 0 || nx >= h || ny < 0 || ny >= w) continue;
            if (grid[nx][ny] == '.') continue;
            if (visit[nx][ny]) continue;
            visit[nx][ny] = 1;
            int nnum = num;
            if (grid[x][y] != grid[nx][ny]) nnum++;
            ans = max(ans,nnum);
            //cout << nx << " " << ny << " " << nnum << "\n";
            pq.push(i3(nnum,ii(nx,ny)));
        }
    }
    cout << ans;
}

Subtask #1

30.0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	67 ms	1796 KB	Output is correct
2	Correct	2 ms	384 KB	Output is correct
3	Correct	3 ms	384 KB	Output is correct
4	Correct	53 ms	1408 KB	Output is correct
5	Correct	10 ms	768 KB	Output is correct
6	Correct	2 ms	256 KB	Output is correct
7	Correct	2 ms	256 KB	Output is correct
8	Correct	4 ms	384 KB	Output is correct
9	Correct	3 ms	384 KB	Output is correct
10	Correct	14 ms	640 KB	Output is correct
11	Correct	12 ms	640 KB	Output is correct
12	Correct	28 ms	896 KB	Output is correct
13	Correct	12 ms	768 KB	Output is correct
14	Correct	15 ms	768 KB	Output is correct
15	Correct	52 ms	1664 KB	Output is correct
16	Correct	63 ms	1656 KB	Output is correct
17	Correct	38 ms	1536 KB	Output is correct
18	Correct	38 ms	1472 KB	Output is correct

Subtask #2

52.5 / 70.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	512 KB	Output is correct
2	Correct	268 ms	8028 KB	Output is correct
3	Correct	1289 ms	78800 KB	Output is correct
4	Correct	361 ms	18700 KB	Output is correct
5	Correct	593 ms	44412 KB	Output is correct
6	Execution timed out	2056 ms	91292 KB	Time limit exceeded
7	Correct	5 ms	512 KB	Output is correct
8	Correct	5 ms	512 KB	Output is correct
9	Correct	10 ms	768 KB	Output is correct
10	Correct	6 ms	512 KB	Output is correct
11	Correct	5 ms	512 KB	Output is correct
12	Correct	4 ms	380 KB	Output is correct
13	Correct	223 ms	8156 KB	Output is correct
14	Correct	146 ms	4912 KB	Output is correct
15	Correct	73 ms	5240 KB	Output is correct
16	Correct	92 ms	3576 KB	Output is correct
17	Correct	572 ms	20336 KB	Output is correct
18	Correct	343 ms	19960 KB	Output is correct
19	Correct	331 ms	18680 KB	Output is correct
20	Correct	307 ms	17076 KB	Output is correct
21	Correct	818 ms	45824 KB	Output is correct
22	Correct	638 ms	44552 KB	Output is correct
23	Correct	1158 ms	38392 KB	Output is correct
24	Correct	583 ms	44832 KB	Output is correct
25	Correct	1314 ms	78584 KB	Output is correct
26	Execution timed out	2055 ms	60452 KB	Time limit exceeded
27	Execution timed out	2053 ms	80512 KB	Time limit exceeded
28	Execution timed out	2045 ms	91332 KB	Time limit exceeded
29	Execution timed out	2041 ms	91336 KB	Time limit exceeded
30	Execution timed out	2057 ms	89748 KB	Time limit exceeded
31	Execution timed out	2054 ms	51572 KB	Time limit exceeded
32	Execution timed out	2060 ms	80420 KB	Time limit exceeded