Submission #722560

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
722560	2023-04-12T09:45:00 Z	PoPularPlusPlus	Tracks in the Snow (BOI13_tracks)	C++17	100 / 100	1858 ms	650896 KB

tracks

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long 
#define pb(e) push_back(e)
#define sv(a) sort(a.begin(),a.end())
#define sa(a,n) sort(a,a+n)
#define mp(a,b) make_pair(a,b)
#define vf first
#define vs second
#define ar array
#define all(x) x.begin(),x.end()
const int inf = 0x3f3f3f3f;
const int mod = 1000000007; 
const double PI=3.14159265358979323846264338327950288419716939937510582097494459230;

mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());

bool remender(ll a , ll b){return a%b;}

//freopen("problemname.in", "r", stdin);
//freopen("problemname.out", "w", stdout);

int n , m;

int convert(int r , int w){
	return r*m+w;
}

pair<int,int> back(int x){
	return mp(x/m,x%m);
}

struct ufds {
	
	vector<int> siz,p;
	
	void init(int nn){
		siz.resize(nn + 1);
		p.resize(nn + 1);
		for(int i = 0; i <= nn; i++){
			siz[i] = 1;
			p[i] = i;
		}
	}
	
	int get(int x){
		return p[x] = (p[x] == x ? x : get(p[x]));
	}
	
	void unio(int x , int y){
		x = get(x);
		y = get(y);
		if(x == y)return;
		if(siz[y] > siz[x])swap(x,y);
		p[y] = x;
		siz[x] += siz[y];
	}
};

int dx[4] = {1,0}, dy[4] = {0,1};

void solve(){
	cin >> n;
	cin >> m;
	char arr[n][m];
	for(int i = 0; i < n; i++){
		for(int j = 0; j < m; j++)cin >> arr[i][j];
	}
	ufds dsu;
	dsu.init(n*m+1);
	for(int i = 0; i < n; i++){
		for(int j = 0; j < m; j++){
			if(arr[i][j] == '.')continue;
			for(int k = 0; k < 2; k++){
				int ni = i + dx[k] , nj = j + dy[k];
				if(ni < n && nj < m && ni >= 0 && nj >= 0 && arr[i][j] == arr[ni][nj]){
					dsu.unio(convert(i,j),convert(ni,nj));
				}
			}
		}
	}
	vector<int> adj[n*m];
	for(int i = 0; i < n; i++){
		for(int j = 0; j < m; j++){
			if(arr[i][j] == '.')continue;
			for(int k = 0; k < 2; k++){
				int ni = i + dx[k] , nj = j + dy[k];
				if(ni < n && ni >= 0 && nj < m && nj >= 0 && arr[ni][nj]!='.'){
					int a = convert(ni,nj);
					int b = convert(i,j);
					a = dsu.get(a);
					b = dsu.get(b);
					if(a==b)continue;
					adj[a].pb(b);
					adj[b].pb(a);
				}
			}
		}
	}
	int dis[n*m];
	queue<int> q;
	memset(dis,-1,sizeof dis);
	dis[dsu.get(0)] = 1;
	q.push(dsu.get(0));
	int ans = 1;
	while(q.size()){
		int node = q.front();
		q.pop();
		for(int i : adj[node]){
			int par = dsu.get(i);
			if(dis[par] == -1){
				dis[par] = dis[node] + 1;
				ans = dis[par];
				q.push(par);
			}
		}
	}
	cout << ans << '\n';
}

int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
   // int t;cin>>t;
   // while(t--){
		solve();
	//}
	return 0;
}

Subtask #1

30.0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	42 ms	12236 KB	Output is correct
2	Correct	1 ms	340 KB	Output is correct
3	Correct	1 ms	340 KB	Output is correct
4	Correct	16 ms	6524 KB	Output is correct
5	Correct	5 ms	3620 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	468 KB	Output is correct
9	Correct	1 ms	596 KB	Output is correct
10	Correct	6 ms	3016 KB	Output is correct
11	Correct	5 ms	1876 KB	Output is correct
12	Correct	13 ms	4564 KB	Output is correct
13	Correct	6 ms	3688 KB	Output is correct
14	Correct	7 ms	3632 KB	Output is correct
15	Correct	32 ms	11900 KB	Output is correct
16	Correct	47 ms	12112 KB	Output is correct
17	Correct	23 ms	10516 KB	Output is correct
18	Correct	16 ms	6448 KB	Output is correct

Subtask #2

70.0 / 70.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	2260 KB	Output is correct
2	Correct	149 ms	65892 KB	Output is correct
3	Correct	1048 ms	633732 KB	Output is correct
4	Correct	284 ms	144600 KB	Output is correct
5	Correct	759 ms	467204 KB	Output is correct
6	Correct	1700 ms	633052 KB	Output is correct
7	Correct	3 ms	2004 KB	Output is correct
8	Correct	3 ms	2240 KB	Output is correct
9	Correct	5 ms	2772 KB	Output is correct
10	Correct	2 ms	1492 KB	Output is correct
11	Correct	3 ms	2132 KB	Output is correct
12	Correct	3 ms	1492 KB	Output is correct
13	Correct	144 ms	65648 KB	Output is correct
14	Correct	91 ms	38028 KB	Output is correct
15	Correct	84 ms	40936 KB	Output is correct
16	Correct	70 ms	28040 KB	Output is correct
17	Correct	380 ms	169212 KB	Output is correct
18	Correct	326 ms	162376 KB	Output is correct
19	Correct	251 ms	144444 KB	Output is correct
20	Correct	230 ms	137356 KB	Output is correct
21	Correct	539 ms	369344 KB	Output is correct
22	Correct	770 ms	466892 KB	Output is correct
23	Correct	744 ms	323912 KB	Output is correct
24	Correct	554 ms	376300 KB	Output is correct
25	Correct	1555 ms	650896 KB	Output is correct
26	Correct	985 ms	443772 KB	Output is correct
27	Correct	1278 ms	582724 KB	Output is correct
28	Correct	1733 ms	633028 KB	Output is correct
29	Correct	1626 ms	624240 KB	Output is correct
30	Correct	1500 ms	599004 KB	Output is correct
31	Correct	1858 ms	499592 KB	Output is correct
32	Correct	1243 ms	585964 KB	Output is correct