Submission #938027

#	Time	Username	Problem	Language	Result	Execution time	Memory
938027		TAhmed33	Tracks in the Snow (BOI13_tracks)	C++98	84.69 / 100	1656 ms	1048576 KiB

tracks

    #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 / 30
• Subtask 2: 54.6875 / 70