Submission #111757

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
111757	2019-05-16T06:20:32 Z	rajarshi_basu	Tracks in the Snow (BOI13_tracks)	C++14	82.5 / 100	2000 ms	495568 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[4000][4000];
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[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;
		//getEdges(e.ss/m,e.ss%m,v);
		int i = e.ss/m;
		int j = e.ss%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]),v);
			v.pb({(i-1)*m+j,cost(grid[i][j],grid[i-1][j])});
		}
		if(j > 0 and cost(grid[i][j],grid[i][j-1])>=0){
			v.pb({(i)*m+j-1,cost(grid[i][j],grid[i][j-1])});
			//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){
			v.pb({(i+1)*m+j,cost(grid[i][j],grid[i+1][j])});
			//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){
			v.pb({(i)*m+j+1,cost(grid[i][j],grid[i][j+1])});
			//insertEdge(change(i,j),change(i,j+1),cost(grid[i][j],grid[i][j+1]),v);
		}
		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});
			}
			//pq.push({dist[e.ss]+f.ss,f.ff});
		}
	}
	
	

	//return 0;
	int mx = 0;
	FOR(i,n){
		FOR(j,m){
			if(grid[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	461 ms	441072 KB	Output is correct
2	Correct	370 ms	438780 KB	Output is correct
3	Correct	376 ms	438968 KB	Output is correct
4	Correct	414 ms	441268 KB	Output is correct
5	Correct	388 ms	439948 KB	Output is correct
6	Correct	375 ms	438764 KB	Output is correct
7	Correct	370 ms	438908 KB	Output is correct
8	Correct	402 ms	439032 KB	Output is correct
9	Correct	393 ms	439280 KB	Output is correct
10	Correct	372 ms	439800 KB	Output is correct
11	Correct	363 ms	439820 KB	Output is correct
12	Correct	400 ms	440016 KB	Output is correct
13	Correct	412 ms	440116 KB	Output is correct
14	Correct	396 ms	440036 KB	Output is correct
15	Correct	452 ms	441172 KB	Output is correct
16	Correct	417 ms	441300 KB	Output is correct
17	Correct	435 ms	440796 KB	Output is correct
18	Correct	446 ms	441316 KB	Output is correct

Subtask #2

52.5 / 70.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	418 ms	453728 KB	Output is correct
2	Correct	559 ms	445432 KB	Output is correct
3	Correct	1109 ms	470188 KB	Output is correct
4	Correct	527 ms	449852 KB	Output is correct
5	Correct	890 ms	459384 KB	Output is correct
6	Execution timed out	2059 ms	493040 KB	Time limit exceeded
7	Correct	400 ms	454404 KB	Output is correct
8	Correct	398 ms	453624 KB	Output is correct
9	Correct	431 ms	438940 KB	Output is correct
10	Correct	384 ms	438776 KB	Output is correct
11	Correct	442 ms	454060 KB	Output is correct
12	Correct	395 ms	439288 KB	Output is correct
13	Correct	553 ms	445384 KB	Output is correct
14	Correct	486 ms	443196 KB	Output is correct
15	Correct	461 ms	443652 KB	Output is correct
16	Correct	496 ms	441036 KB	Output is correct
17	Correct	746 ms	450680 KB	Output is correct
18	Correct	724 ms	450452 KB	Output is correct
19	Correct	541 ms	449996 KB	Output is correct
20	Correct	555 ms	449068 KB	Output is correct
21	Correct	845 ms	460276 KB	Output is correct
22	Correct	880 ms	459384 KB	Output is correct
23	Correct	1380 ms	456408 KB	Output is correct
24	Correct	814 ms	459920 KB	Output is correct
25	Correct	1555 ms	470248 KB	Output is correct
26	Execution timed out	2097 ms	464652 KB	Time limit exceeded
27	Execution timed out	2068 ms	472524 KB	Time limit exceeded
28	Execution timed out	2092 ms	493100 KB	Time limit exceeded
29	Execution timed out	2081 ms	490996 KB	Time limit exceeded
30	Execution timed out	2064 ms	495568 KB	Time limit exceeded
31	Execution timed out	2085 ms	463196 KB	Time limit exceeded
32	Execution timed out	2086 ms	471288 KB	Time limit exceeded