Submission #462433

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
462433	2021-08-10T14:15:38 Z	Khizri	Tracks in the Snow (BOI13_tracks)	C++17	78.125 / 100	2000 ms	1048576 KB

tracks

#include <bits/stdc++.h>
using namespace std;
//------------------------------DEFINE------------------------------
//******************************************************************
#define IOS ios_base::sync_with_stdio(false); cin.tie(0),cout.tie(0)
#define ll long long
#define pb push_back		 
#define F first																 
#define S second 															 
#define INF 1e18
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define pii pair<int,int>
#define pll pair<ll,ll>
#define OK cout<<"Ok"<<endl;
#define MOD (ll)(1e9+7)
#define endl "\n"
//******************************************************************
//----------------------------FUNCTION------------------------------
//******************************************************************
ll gcd(ll a,ll b){
	if(a>b) swap(a,b);
	if(a==0) return a+b;
	return gcd(b%a,a);
}
ll lcm(ll a,ll b){
	return a/gcd(a,b)*b;
}
bool is_prime(ll n){
	ll k=sqrt(n);
	if(n==2) return true;
	if(n<2||n%2==0||k*k==n) return false;
	for(int i=3;i<=k;i+=2){
		if(n%i==0){
			return false;
		}
	}
	return true;
}
//*****************************************************************
//--------------------------MAIN-CODE------------------------------
const int mxn=4000+5;
const int N=1e7;
int t=1,n,m,k,a,b,x[mxn][mxn],dis[N],color[mxn][mxn],colorr[N];
char arr[mxn][mxn];
char c[3];
map<pii,bool>edge;
vector<int>vt[N];
void dfs(int i,int j){
	char cc=arr[i][j];
	color[i][j]=1;
	x[i][j]=k;
	if(arr[i+1][j]==cc&&!color[i+1][j]){
		dfs(i+1,j);
	}
	if(arr[i-1][j]==cc&&!color[i-1][j]){
		dfs(i-1,j);
	}
	if(arr[i][j+1]==cc&&!color[i][j+1]){
		dfs(i,j+1);
	}
	if(arr[i][j-1]==cc&&!color[i][j-1]){
		dfs(i,j-1);
	}
}
void solve(){
	memset(arr,'.',sizeof(arr));
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>arr[i][j];
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(arr[i][j]!='.'&&!color[i][j]){
				k++;
				dfs(i,j);
			}
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(arr[i][j]!=arr[i][j+1]&&arr[i][j]!='.'&&arr[i][j+1]!='.'){
				if(!edge[{x[i][j],x[i][j+1]}]){
					edge[{x[i][j],x[i][j+1]}]=1;
					edge[{x[i][j+1],x[i][j]}]=1;
					vt[x[i][j]].pb(x[i][j+1]);
					vt[x[i][j+1]].pb(x[i][j]);
				}
			}
			if(arr[i][j]!=arr[i][j-1]&&arr[i][j]!='.'&&arr[i][j-1]!='.'){
				if(!edge[{x[i][j],x[i][j-1]}]){
					edge[{x[i][j],x[i][j-1]}]=1;
					edge[{x[i][j-1],x[i][j]}]=1;
					vt[x[i][j]].pb(x[i][j-1]);
					vt[x[i][j-1]].pb(x[i][j]);
				}
			}
			if(arr[i][j]!=arr[i+1][j]&&arr[i][j]!='.'&&arr[i+1][j]!='.'){
				if(!edge[{x[i][j],x[i+1][j]}]){
					edge[{x[i][j],x[i+1][j]}]=1;
					edge[{x[i+1][j],x[i][j]}]=1;
					vt[x[i][j]].pb(x[i+1][j]);
					vt[x[i+1][j]].pb(x[i][j]);
				}
			}
			if(arr[i][j]!=arr[i-1][j]&&arr[i][j]!='.'&&arr[i-1][j]!='.'){
				if(!edge[{x[i][j],x[i-1][j]}]){
					edge[{x[i][j],x[i-1][j]}]=1;
					edge[{x[i-1][j],x[i][j]}]=1;
					vt[x[i][j]].pb(x[i-1][j]);
					vt[x[i-1][j]].pb(x[i][j]);
				}
			}
		}
	}
	queue<int>q;
	q.push(1);
	colorr[1]=1;
	dis[1]=1;
	int ans=1;
	while(q.size()){
		int u=q.front();
		q.pop();
		for(int v:vt[u]){
			if(!colorr[v]){
				dis[v]=dis[u]+1;
				colorr[v]=1;
				q.push(v);
				ans=max(ans,dis[v]);
			}
		}
	}
	cout<<ans<<endl;
}
int main(){
	IOS;
	//cin>>t;
	while(t--){
		solve();
	}
	return 0;
}

Subtask #1

30.0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	242 ms	265364 KB	Output is correct
2	Correct	132 ms	251056 KB	Output is correct
3	Correct	131 ms	251312 KB	Output is correct
4	Correct	154 ms	258032 KB	Output is correct
5	Correct	146 ms	255316 KB	Output is correct
6	Correct	130 ms	250948 KB	Output is correct
7	Correct	132 ms	251240 KB	Output is correct
8	Correct	144 ms	251404 KB	Output is correct
9	Correct	132 ms	251716 KB	Output is correct
10	Correct	148 ms	254792 KB	Output is correct
11	Correct	139 ms	253376 KB	Output is correct
12	Correct	171 ms	256964 KB	Output is correct
13	Correct	148 ms	255264 KB	Output is correct
14	Correct	147 ms	255308 KB	Output is correct
15	Correct	230 ms	264332 KB	Output is correct
16	Correct	266 ms	265276 KB	Output is correct
17	Correct	192 ms	263832 KB	Output is correct
18	Correct	153 ms	258036 KB	Output is correct

Subtask #2

48.125 / 70.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	150 ms	283204 KB	Output is correct
2	Correct	467 ms	305156 KB	Output is correct
3	Execution timed out	2097 ms	591308 KB	Time limit exceeded
4	Correct	557 ms	339528 KB	Output is correct
5	Execution timed out	2095 ms	689300 KB	Time limit exceeded
6	Execution timed out	2071 ms	502696 KB	Time limit exceeded
7	Correct	153 ms	284568 KB	Output is correct
8	Correct	158 ms	283144 KB	Output is correct
9	Correct	146 ms	253344 KB	Output is correct
10	Correct	135 ms	252096 KB	Output is correct
11	Correct	150 ms	283436 KB	Output is correct
12	Correct	142 ms	253976 KB	Output is correct
13	Correct	471 ms	305324 KB	Output is correct
14	Correct	325 ms	284228 KB	Output is correct
15	Correct	346 ms	290588 KB	Output is correct
16	Correct	308 ms	275564 KB	Output is correct
17	Correct	998 ms	381272 KB	Output is correct
18	Correct	1076 ms	389632 KB	Output is correct
19	Correct	565 ms	339376 KB	Output is correct
20	Correct	585 ms	340392 KB	Output is correct
21	Correct	1331 ms	467048 KB	Output is correct
22	Execution timed out	2109 ms	669672 KB	Time limit exceeded
23	Correct	1991 ms	490344 KB	Output is correct
24	Correct	1554 ms	554936 KB	Output is correct
25	Execution timed out	2100 ms	546908 KB	Time limit exceeded
26	Runtime error	826 ms	1048576 KB	Execution killed with signal 9
27	Correct	1522 ms	830688 KB	Output is correct
28	Execution timed out	2078 ms	501156 KB	Time limit exceeded
29	Execution timed out	2090 ms	477444 KB	Time limit exceeded
30	Execution timed out	2069 ms	579244 KB	Time limit exceeded
31	Execution timed out	2108 ms	468264 KB	Time limit exceeded
32	Correct	1727 ms	891496 KB	Output is correct