Submission #111764

#	Time	Username	Problem	Language	Result	Execution time	Memory
111764		rajarshi_basu	Tracks in the Snow (BOI13_tracks)	C++14	82.50 / 100	2132 ms	495576 KiB

tracks

#include <iostream>
#include <vector>
#include <set>
#include <iomanip>
#include <algorithm>
#include <functional>
#include <stdio.h>
#include <cmath>
#include <queue>
#include <string>
#include <map>
#include <complex>
#include <stack>
#include <set>

#define FOR(i,n) for(int i=0;i<n;i++)
#define FORE(i,a,b) for(int i=a;i<=b;i++)
#define ll long long int
#define vi vector<int>
#define ii pair<ll,ll>
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define pll pair<ll,ll>
#define cd complex<double> 

const int INF = 1e9;
using namespace std;
const int MAXN = 4000*4000+500;
vector<ii> g[MAXN];
char grid[MAXN];
int n,m;
inline int cost(char c1,char c2){
	return (c1 == '.' or c2 == '.')?-1:(1-(c1==c2));
}

int dist[MAXN];
bool vis[MAXN];

inline int change(int i,int j){
	return i*m+j;
}

inline void insertEdge(int a,int b,int c,vector<ii>& v){
	v.pb({b,c});
}
/*
inline void getEdges(int i,int j,vector<ii>& v){
	if(i > 0 and cost(grid[i][j],grid[i-1][j])>=0){
				insertEdge(change(i,j),change(i-1,j),cost(grid[i][j],grid[i-1][j]),v);
			}
			if(j > 0 and cost(grid[i][j],grid[i][j-1])>=0){
				insertEdge(change(i,j),change(i,j-1),cost(grid[i][j],grid[i][j-1]),v);
			}
			if(i < n-1 and cost(grid[i][j],grid[i+1][j])>=0){
				insertEdge(change(i,j),change(i+1,j),cost(grid[i][j],grid[i+1][j]),v);
			}
			if(j < m-1 and cost(grid[i][j],grid[i][j+1])>=0){
				insertEdge(change(i,j),change(i,j+1),cost(grid[i][j],grid[i][j+1]),v);
			}

}
*/
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n >> m;
	string s;
	FOR(i,n){
		cin >> s;
		FOR(j,m)grid[change(i,j)] = s[j];
	}
	/*
	FOR(i,n){
		FOR(j,m){
			if(i > 0 and cost(grid[i][j],grid[i-1][j])>=0){
				insertEdge(change(i,j),change(i-1,j),cost(grid[i][j],grid[i-1][j]));
			}
			if(j > 0 and cost(grid[i][j],grid[i][j-1])>=0){
				insertEdge(change(i,j),change(i,j-1),cost(grid[i][j],grid[i][j-1]));
			}
			if(i < n-1 and cost(grid[i][j],grid[i+1][j])>=0){
				insertEdge(change(i,j),change(i+1,j),cost(grid[i][j],grid[i+1][j]));
			}
			if(j < m-1 and cost(grid[i][j],grid[i][j+1])>=0){
				insertEdge(change(i,j),change(i,j+1),cost(grid[i][j],grid[i][j+1]));
			}
		}
	}*/

	FOR(i,MAXN)dist[i] = INF;
	queue<ii> q1;
	queue<ii> q2;
	
	q1.push({0,0});
    
	while(1){
		if(q1.empty() and q2.empty())break;
		if(q1.empty())swap(q1,q2);
		auto e = q1.front();q1.pop();
		if(vis[e.ss])continue;
		vis[e.ss] = 1;
		dist[e.ss] = e.ff;
		vector<ii> v;
		int i = e.ss/m;
		int j = e.ss%m;
		if(i > 0 and cost(grid[change(i,j)],grid[change(i-1,j)])>=0){
			v.pb({(i-1)*m+j,cost(grid[change(i,j)],grid[change(i-1,j)])});
		}
		if(j > 0 and cost(grid[change(i,j)],grid[change(i,j-1)])>=0){
			v.pb({(i)*m+j-1,cost(grid[change(i,j)],grid[change(i,j-1)])});
		}
		if(i < n-1 and cost(grid[change(i,j)],grid[change(i+1,j)])>=0){
			v.pb({(i+1)*m+j,cost(grid[change(i,j)],grid[change(i+1,j)])});
		}
		if(j < m-1 and cost(grid[change(i,j)],grid[change(i,j+1)])>=0){
			v.pb({(i)*m+j+1,cost(grid[change(i,j)],grid[change(i,j+1)])});
		}
		for(auto f : v){
			if(dist[f.ff] <= dist[e.ss]+f.ss)continue;
			if(f.ss == 0){
				q1.push({e.ff,f.ff});
			}else{
				q2.push({e.ff+1,f.ff});
			}
		}
	}
	
	

	//return 0;
	int mx = 0;
	FOR(i,n){
		FOR(j,m){
			if(grid[change(i,j)] != '.'){
				mx = max(mx,dist[change(i,j)]);
			}
		//	cout << setw(10) <<dist[change(i,j)] << " ";
		}
		//cout << endl;
	}
	cout << (mx + 1) << endl;
	return 0;
}

• Subtask 1: 30 / 30
• Subtask 2: 52.5 / 70