oj.uz

Submission #471401

# Submission time Handle Problem Language Result Execution time Memory
471401 2021-09-09T00:48:13 Z YoRepi7 Tracks in the Snow (BOI13_tracks) C++17
36.7708 / 100
 2000 ms 901172 KB 
#include <bits/stdc++.h>
 
using namespace std;
using ll = long long;
using vi = vector<int>;
using vb = vector<bool>;
using vl = vector<ll>;
using pl = pair<ll, ll>;
using pi = pair<int, int>;
using vpl = vector<pl>;
using vpi = vector<pi>;
using vc = vector<char>;
using vs = vector<string>;
 
#define forn(i, n) for(int i = 0; i < n; i++)
#define rofn(i, n) for(int i = n; i >= 0; i--)
#define FOR(i, a, b) for(int i = a; i < b; i++)
#define ROF(i, b, a) for(int i = b; i >= a; i--)
#define TRAV(a, x) for(auto& a: x)
#define ABC(c) for(char c = 'a'; c <= 'z'; c++)
#define all(x) begin(x), end(x)
#define sor(x) sort(all(x))
#define rsor(x) sort(all(x), greater<int>())
#define pb push_back
#define mp make_pair
#define ins insert
#define ub upper_bound
#define lb lower_bound
#define len(x) (int)(x).length()
#define sz(x) (int)(x).size()
#define f first
#define s second
#define dbg(x) TRAV(a, x) cout << a << " "
#define print(x) cout << x << endl
#define traverse(x) TRAV(a, x) cout << a.f << " " << a.s << endl
#define readvi(a, n) forn(i, n) cin >> a[i]
#define readvpi(a, n) forn(i, n) cin >> a[i].f >> a[i].s
#define gcd(a, b) __gcd(a, b)

const int MAXN = 4000, INF = 1e9;

char grid[MAXN][MAXN]; int vis[MAXN][MAXN], comp[MAXN][MAXN], h, w, cur;

int xDir[4] = {1, -1, 0, 0}, yDir[4] = {0, 0, 1, -1};

bool vis1[MAXN * MAXN + 1];

void floodfill(int i, int j, char animal){
	if(i >= h || j >= w || i < 0 || j < 0 || grid[i][j] != animal || vis[i][j]){
		return;
	}
	vis[i][j] = true;
	comp[i][j] = cur;
	forn(k, 4){
		floodfill(i + xDir[k], j + yDir[k], animal);
	}
}

void solve(){
	cin >> h >> w;
	forn(i, h){
		forn(j, w){
			cin >> grid[i][j];
		}
	}
	cur = 1;
	forn(i, h){
		forn(j, w){
			if(grid[i][j] != '.' && !vis[i][j]){
				floodfill(i, j, grid[i][j]);
				++cur;
			}
		}
	}
	vi adj[cur + 1], dist(cur + 1, INF);
	forn(i, h){
		forn(j, w){
			if(comp[i][j]){
				forn(k, 4){
					int x = i + xDir[k], y = j + yDir[k];
					if(x && y && comp[x][y] && (comp[x][y] != comp[i][j])){
						adj[comp[i][j]].pb(comp[x][y]);
						adj[comp[x][y]].pb(comp[i][j]);
					}
				}
			}
		}
	}
	queue<int> q;
	q.push(comp[0][0]);
	dist[comp[0][0]] = 0;
	while(!q.empty()){
		int cur = q.front();
		q.pop();
		if(vis1[cur]){
			continue;
		}
		vis1[cur] = true;
		TRAV(a, adj[cur]){
			if(dist[a] > dist[cur] + 1){
				dist[a] = dist[cur] + 1;
			}
			q.push(a);
		}
	}
	int ans = 0;
	FOR(i, 1, cur){
		ans = max(ans, dist[i]);
	}
	cout << ++ans << endl;
}

int main(){
	ios::sync_with_stdio(0); cin.tie(0);
	// int t; cin >> t;
	// forn(i, t){
	// 	solve();
	// }
	solve();
}

Subtask #1
8.33333333333 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 53 ms 14788 KB Output isn't correct
2 Incorrect 1 ms 460 KB Output isn't correct
3 Incorrect 1 ms 972 KB Output isn't correct
4 Correct 19 ms 9416 KB Output is correct
5 Incorrect 8 ms 4944 KB Output isn't correct
6 Incorrect 1 ms 588 KB Output isn't correct
7 Incorrect 1 ms 972 KB Output isn't correct
8 Correct 2 ms 1100 KB Output is correct
9 Correct 2 ms 1612 KB Output is correct
10 Incorrect 8 ms 4320 KB Output isn't correct
11 Correct 6 ms 3532 KB Output is correct
12 Incorrect 20 ms 6808 KB Output isn't correct
13 Incorrect 10 ms 4940 KB Output isn't correct
14 Incorrect 8 ms 4940 KB Output isn't correct
15 Incorrect 45 ms 13096 KB Output isn't correct
16 Incorrect 53 ms 14752 KB Output isn't correct
17 Incorrect 35 ms 11084 KB Output isn't correct
18 Correct 19 ms 9444 KB Output is correct

Subtask #2
28.4375 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 46456 KB Output is correct
2 Incorrect 174 ms 42024 KB Output isn't correct
3 Incorrect 999 ms 227000 KB Output isn't correct
4 Correct 231 ms 70852 KB Output is correct
5 Correct 1194 ms 354388 KB Output is correct
6 Incorrect 1751 ms 319856 KB Output isn't correct
7 Incorrect 29 ms 48560 KB Output isn't correct
8 Correct 29 ms 46520 KB Output is correct
9 Incorrect 7 ms 1740 KB Output isn't correct
10 Runtime error 10 ms 1380 KB Execution killed with signal 11
11 Correct 29 ms 47564 KB Output is correct
12 Correct 5 ms 2892 KB Output is correct
13 Incorrect 179 ms 41940 KB Output isn't correct
14 Incorrect 110 ms 27104 KB Output isn't correct
15 Incorrect 78 ms 29424 KB Output isn't correct
16 Incorrect 87 ms 18784 KB Output isn't correct
17 Incorrect 473 ms 92992 KB Output isn't correct
18 Incorrect 281 ms 92004 KB Output isn't correct
19 Correct 242 ms 70968 KB Output is correct
20 Correct 249 ms 66628 KB Output is correct
21 Incorrect 533 ms 149440 KB Output isn't correct
22 Correct 1182 ms 354412 KB Output is correct
23 Incorrect 891 ms 162748 KB Output isn't correct
24 Incorrect 581 ms 166340 KB Output isn't correct
25 Incorrect 1696 ms 292824 KB Output isn't correct
26 Correct 1881 ms 901172 KB Output is correct
27 Correct 1414 ms 366724 KB Output is correct
28 Incorrect 1775 ms 319964 KB Output isn't correct
29 Incorrect 1644 ms 298244 KB Output isn't correct
30 Correct 1635 ms 309696 KB Output is correct
31 Execution timed out 2089 ms 398092 KB Time limit exceeded
32 Correct 1606 ms 387696 KB Output is correct