oj.uz

Submission #938027

# Submission time Handle Problem Language Result Execution time Memory
938027 2024-03-04T18:08:19 Z TAhmed33 Tracks in the Snow (BOI13_tracks) C++
84.6875 / 100
 1656 ms 1048576 KB 
    #include <bits/stdc++.h>
    using namespace std;
    #define int long long
    int dx[4] = {0, -1, 0, 1};
    int dy[4] = {1, 0, -1, 0};
    int comp[4001][4001] = {};
    char arr[4001][4001]; 
    int n, m;
    bool check (int i, int j) {
    	return (i >= 1 && i <= n && j >= 1 && j <= m && arr[i][j] != '.');
    }
    void dfs (int i, int j) {
    	for (int l = 0; l < 4; l++) {
    		if (check(i + dx[l], j + dy[l]) && comp[i + dx[l]][j + dy[l]] == 0 && arr[i + dx[l]][j + dy[l]] == arr[i][j]) {
    			comp[i + dx[l]][j + dy[l]] = comp[i][j];
    			dfs(i + dx[l], j + dy[l]);
    		}
    	}
    }
    vector <int> adj[1000001];
    bool vis[1000001];
    signed main () {
    	memset(vis, false, sizeof(vis));
    	cin >> n >> m; for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) cin >> arr[i][j];
    	int c = 0;
    	for (int i = 1; i <= n; i++) {
    		for (int j = 1; j <= m; j++) {
    			if (comp[i][j] == 0 && arr[i][j] != '.') {
    				c++;
    				comp[i][j] = c;
    				dfs(i, j);
    			}
    		}
    	}
    	for (int i = 1; i <= n; i++) {
    		for (int j = 1; j <= m; j++) {
    			if (arr[i][j] == '.') continue;
    			for (int l = 0; l < 4; l++) {
    				if (check(i + dx[l], j + dy[l])) {
    					if (comp[i + dx[l]][j + dy[l]] != comp[i][j]) {
    						adj[comp[i][j]].push_back(comp[i + dx[l]][j + dy[l]]);
    						adj[comp[i + dx[l]][j + dy[l]]].push_back(comp[i][j]);
    					}
    				}
    			}
    		}
    	}
     
    	queue <int> cur;
    	cur.push(comp[1][1]); vis[comp[1][1]] = 1;
    	int cnt = 1;
    	int ans = 0;
    	while (!cur.empty()) {
    		auto u = cur.size(); while (u--) {
    			int k = cur.front(); cur.pop(); 
    			ans = cnt;
    			for (auto j : adj[k]) if (!vis[j]) {
                  vis[j] = 1; cur.push(j);
                }
    		}
    		cnt++;
    	}
    	cout << ans << '\n';
    }

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 41552 KB Output is correct
2 Correct 6 ms 25432 KB Output is correct
3 Correct 6 ms 25436 KB Output is correct
4 Correct 22 ms 33740 KB Output is correct
5 Correct 13 ms 29528 KB Output is correct
6 Correct 6 ms 25180 KB Output is correct
7 Correct 6 ms 25436 KB Output is correct
8 Correct 6 ms 25692 KB Output is correct
9 Correct 7 ms 27740 KB Output is correct
10 Correct 13 ms 29408 KB Output is correct
11 Correct 10 ms 29384 KB Output is correct
12 Correct 20 ms 32604 KB Output is correct
13 Correct 13 ms 29644 KB Output is correct
14 Correct 18 ms 29684 KB Output is correct
15 Correct 41 ms 38484 KB Output is correct
16 Correct 47 ms 41552 KB Output is correct
17 Correct 34 ms 34900 KB Output is correct
18 Correct 21 ms 33748 KB Output is correct

Subtask #2
54.6875 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 57680 KB Output is correct
2 Correct 156 ms 67668 KB Output is correct
3 Runtime error 1018 ms 389116 KB Execution killed with signal 11
4 Correct 237 ms 88144 KB Output is correct
5 Runtime error 581 ms 282756 KB Execution killed with signal 11
6 Correct 1500 ms 437568 KB Output is correct
7 Correct 18 ms 58456 KB Output is correct
8 Correct 17 ms 57692 KB Output is correct
9 Correct 11 ms 26712 KB Output is correct
10 Correct 7 ms 25688 KB Output is correct
11 Correct 18 ms 58056 KB Output is correct
12 Correct 8 ms 28508 KB Output is correct
13 Correct 152 ms 67808 KB Output is correct
14 Correct 100 ms 51492 KB Output is correct
15 Correct 79 ms 48976 KB Output is correct
16 Correct 77 ms 46132 KB Output is correct
17 Correct 377 ms 120508 KB Output is correct
18 Correct 303 ms 102744 KB Output is correct
19 Correct 241 ms 88156 KB Output is correct
20 Correct 240 ms 85500 KB Output is correct
21 Correct 597 ms 159496 KB Output is correct
22 Runtime error 575 ms 282704 KB Execution killed with signal 11
23 Correct 738 ms 198784 KB Output is correct
24 Runtime error 604 ms 262444 KB Execution killed with signal 11
25 Runtime error 1020 ms 447884 KB Execution killed with signal 11
26 Runtime error 973 ms 1048576 KB Execution killed with signal 9
27 Correct 1321 ms 688584 KB Output is correct
28 Correct 1509 ms 438724 KB Output is correct
29 Correct 1427 ms 434624 KB Output is correct
30 Correct 1380 ms 510652 KB Output is correct
31 Runtime error 1656 ms 940884 KB Execution killed with signal 11
32 Correct 1263 ms 597412 KB Output is correct