Submission #111764

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
111764	2019-05-16T06:27:27 Z	rajarshi_basu	Tracks in the Snow (BOI13_tracks)	C++14	82.5 / 100	2000 ms	495576 KB

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.0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	463 ms	439588 KB	Output is correct
2	Correct	380 ms	438776 KB	Output is correct
3	Correct	388 ms	438748 KB	Output is correct
4	Correct	419 ms	439544 KB	Output is correct
5	Correct	405 ms	439020 KB	Output is correct
6	Correct	393 ms	438852 KB	Output is correct
7	Correct	367 ms	438776 KB	Output is correct
8	Correct	399 ms	438904 KB	Output is correct
9	Correct	412 ms	438800 KB	Output is correct
10	Correct	404 ms	438904 KB	Output is correct
11	Correct	409 ms	439092 KB	Output is correct
12	Correct	418 ms	439104 KB	Output is correct
13	Correct	410 ms	438932 KB	Output is correct
14	Correct	437 ms	438904 KB	Output is correct
15	Correct	420 ms	439292 KB	Output is correct
16	Correct	477 ms	439416 KB	Output is correct
17	Correct	456 ms	439348 KB	Output is correct
18	Correct	440 ms	439416 KB	Output is correct

Subtask #2

52.5 / 70.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	418 ms	438900 KB	Output is correct
2	Correct	496 ms	441848 KB	Output is correct
3	Correct	1057 ms	470160 KB	Output is correct
4	Correct	528 ms	446200 KB	Output is correct
5	Correct	1046 ms	456440 KB	Output is correct
6	Execution timed out	2079 ms	492780 KB	Time limit exceeded
7	Correct	364 ms	438820 KB	Output is correct
8	Correct	353 ms	438904 KB	Output is correct
9	Correct	429 ms	439032 KB	Output is correct
10	Correct	431 ms	438904 KB	Output is correct
11	Correct	415 ms	438896 KB	Output is correct
12	Correct	415 ms	438980 KB	Output is correct
13	Correct	511 ms	441884 KB	Output is correct
14	Correct	447 ms	440632 KB	Output is correct
15	Correct	425 ms	440872 KB	Output is correct
16	Correct	515 ms	440184 KB	Output is correct
17	Correct	812 ms	446840 KB	Output is correct
18	Correct	561 ms	446588 KB	Output is correct
19	Correct	500 ms	446244 KB	Output is correct
20	Correct	504 ms	445432 KB	Output is correct
21	Correct	813 ms	457040 KB	Output is correct
22	Correct	1002 ms	456312 KB	Output is correct
23	Correct	1291 ms	454008 KB	Output is correct
24	Correct	709 ms	456580 KB	Output is correct
25	Correct	1679 ms	470008 KB	Output is correct
26	Execution timed out	2132 ms	462840 KB	Time limit exceeded
27	Execution timed out	2074 ms	472440 KB	Time limit exceeded
28	Execution timed out	2082 ms	493056 KB	Time limit exceeded
29	Execution timed out	2094 ms	491024 KB	Time limit exceeded
30	Execution timed out	2082 ms	495576 KB	Time limit exceeded
31	Execution timed out	2050 ms	460696 KB	Time limit exceeded
32	Execution timed out	2092 ms	471876 KB	Time limit exceeded