Submission #625275

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
625275	2022-08-09T18:31:58 Z	eNGy	Tracks in the Snow (BOI13_tracks)	C++17	97.8125 / 100	1947 ms	1048576 KB

tracks

#include <bits/stdc++.h>
#include <iostream>
#define c(x) (cerr << __LINE__ << ": " << #x << ' ' << (x) << endl, (x))
#define vis() (cerr << __LINE__ << endl)
#define ll long long
#define f first
#define s second
#define pb push_back
#define rsz resize
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define mp make_pair

using namespace std;

vector<string> F;
vector<vector<int>> G;
vector<set<int>> A;
int N, M; 

bool ok(int I, int J){
	if(I < 0 || I >= N || J < 0 || J >= M) return false;
	return true;
}

void dfs(int I, int J, char a, int e){
	if(!ok(I, J)) return;
	if(F[I][J] != a || G[I][J]) return;

	G[I][J] = e;

	if(ok(I+1, J)){
		int b = G[I+1][J];
		if(b != 0 && b != e){
			A[b].insert(e);
			A[e].insert(b);
		}
	}
	
	if(ok(I, J+1)){
		int b = G[I][J+1];
		if(b != 0 && b != e){
			A[b].insert(e);
			A[e].insert(b);
		}
	}

	if(ok(I-1, J)){
		int b = G[I-1][J];
		if(b != 0 && b != e){
			A[b].insert(e);
			A[e].insert(b);
		}
	}

	if(ok(I, J-1)){
		int b = G[I][J-1];
		if(b != 0 && b != e){
			A[b].insert(e);
			A[e].insert(b);
		}
	}

	dfs(I+1, J, a, e);
	dfs(I, J+1, a, e);
	dfs(I-1, J, a, e);
	dfs(I, J-1, a, e);
}

int bfs(){
	int D = A.size();
	vector<bool> V(D);
	queue<pair<int, int>> q;
	q.push({1, 1});

	int ris = 0;
	while(!q.empty()){
		int n = q.front().f, d = q.front().s;
		q.pop();

		if(V[n]) continue;
		V[n] = true;

		ris = max(ris, d);

		for(int v: A[n]){
			q.push({v, d+1});
		}
	}

	return ris;
}

int main(){
	ifstream in("input.txt");
	ofstream out("output.txt");

	cin >> N >> M;

	F.resize(N);
	for(int i=0; i<N; i++){
		cin >> F[i];
	}
	

	G.resize(N, vector<int>(M, 0));

	A.pb(set<int>());
	int e = 1;
	for(int i=0; i<N; i++){
		for(int j=0; j<M; j++){
			if(!G[i][j] && F[i][j] != '.'){
				A.pb(set<int>());
				dfs(i, j, F[i][j], e);
				e++;
			}
		}
	}
	

	cout << bfs();
}

Subtask #1

30.0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	43 ms	10368 KB	Output is correct
2	Correct	1 ms	340 KB	Output is correct
3	Correct	1 ms	340 KB	Output is correct
4	Correct	15 ms	3284 KB	Output is correct
5	Correct	6 ms	2144 KB	Output is correct
6	Correct	1 ms	340 KB	Output is correct
7	Correct	1 ms	340 KB	Output is correct
8	Correct	1 ms	340 KB	Output is correct
9	Correct	1 ms	468 KB	Output is correct
10	Correct	6 ms	2064 KB	Output is correct
11	Correct	4 ms	1364 KB	Output is correct
12	Correct	14 ms	3428 KB	Output is correct
13	Correct	6 ms	2192 KB	Output is correct
14	Correct	6 ms	2168 KB	Output is correct
15	Correct	33 ms	9476 KB	Output is correct
16	Correct	42 ms	10216 KB	Output is correct
17	Correct	26 ms	9344 KB	Output is correct
18	Correct	13 ms	3372 KB	Output is correct

Subtask #2

67.8125 / 70.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	2068 KB	Output is correct
2	Correct	137 ms	40832 KB	Output is correct
3	Correct	890 ms	312464 KB	Output is correct
4	Correct	216 ms	61724 KB	Output is correct
5	Correct	1449 ms	836752 KB	Output is correct
6	Correct	1655 ms	270480 KB	Output is correct
7	Correct	4 ms	2132 KB	Output is correct
8	Correct	4 ms	2112 KB	Output is correct
9	Correct	6 ms	2296 KB	Output is correct
10	Correct	2 ms	1468 KB	Output is correct
11	Correct	4 ms	1760 KB	Output is correct
12	Correct	4 ms	2044 KB	Output is correct
13	Correct	134 ms	40672 KB	Output is correct
14	Correct	85 ms	24368 KB	Output is correct
15	Correct	87 ms	31272 KB	Output is correct
16	Correct	72 ms	18936 KB	Output is correct
17	Correct	348 ms	105876 KB	Output is correct
18	Correct	369 ms	123076 KB	Output is correct
19	Correct	201 ms	61356 KB	Output is correct
20	Correct	222 ms	73396 KB	Output is correct
21	Correct	514 ms	179860 KB	Output is correct
22	Correct	1385 ms	836436 KB	Output is correct
23	Correct	663 ms	197740 KB	Output is correct
24	Correct	637 ms	260016 KB	Output is correct
25	Correct	1443 ms	488656 KB	Output is correct
26	Runtime error	842 ms	1048576 KB	Execution killed with signal 9
27	Correct	1579 ms	1048576 KB	Output is correct
28	Correct	1596 ms	270456 KB	Output is correct
29	Correct	1556 ms	277136 KB	Output is correct
30	Correct	1479 ms	463948 KB	Output is correct
31	Correct	1947 ms	335132 KB	Output is correct
32	Correct	1560 ms	962272 KB	Output is correct