Submission #111749

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
111749	2019-05-16T06:10:49 Z	rajarshi_basu	Tracks in the Snow (BOI13_tracks)	C++14	82.5 / 100	2000 ms	510976 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);
			}
			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);
			}
		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});
		}
	}/*
	while(!pq.empty()){
		auto e = pq.front();pq.pop();
		if(dist[e.ss] <= e.ff)continue;
		dist[e.ss] = e.ff;
		vector<ii> v;
		getEdges(e.ss/m,e.ss%m,v);
		for(auto f : v){
			if(dist[f.ff] <= dist[e.ss]+f.ss)continue;
			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	497 ms	441448 KB	Output is correct
2	Correct	395 ms	438776 KB	Output is correct
3	Correct	388 ms	438964 KB	Output is correct
4	Correct	445 ms	441412 KB	Output is correct
5	Correct	394 ms	440056 KB	Output is correct
6	Correct	403 ms	438844 KB	Output is correct
7	Correct	396 ms	438920 KB	Output is correct
8	Correct	396 ms	438908 KB	Output is correct
9	Correct	381 ms	439092 KB	Output is correct
10	Correct	417 ms	440056 KB	Output is correct
11	Correct	417 ms	439776 KB	Output is correct
12	Correct	485 ms	440184 KB	Output is correct
13	Correct	405 ms	440064 KB	Output is correct
14	Correct	403 ms	440232 KB	Output is correct
15	Correct	441 ms	441216 KB	Output is correct
16	Correct	472 ms	441352 KB	Output is correct
17	Correct	429 ms	441092 KB	Output is correct
18	Correct	486 ms	441484 KB	Output is correct

Subtask #2

52.5 / 70.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	440 ms	453812 KB	Output is correct
2	Correct	607 ms	446692 KB	Output is correct
3	Correct	1264 ms	485864 KB	Output is correct
4	Correct	562 ms	453496 KB	Output is correct
5	Correct	999 ms	468260 KB	Output is correct
6	Execution timed out	2052 ms	508548 KB	Time limit exceeded
7	Correct	422 ms	454520 KB	Output is correct
8	Correct	425 ms	453752 KB	Output is correct
9	Correct	371 ms	439032 KB	Output is correct
10	Correct	390 ms	438776 KB	Output is correct
11	Correct	429 ms	454136 KB	Output is correct
12	Correct	397 ms	439392 KB	Output is correct
13	Correct	591 ms	446704 KB	Output is correct
14	Correct	500 ms	444092 KB	Output is correct
15	Correct	461 ms	444664 KB	Output is correct
16	Correct	531 ms	441720 KB	Output is correct
17	Correct	868 ms	454704 KB	Output is correct
18	Correct	655 ms	454384 KB	Output is correct
19	Correct	620 ms	453580 KB	Output is correct
20	Correct	619 ms	452436 KB	Output is correct
21	Correct	930 ms	469240 KB	Output is correct
22	Correct	957 ms	468128 KB	Output is correct
23	Correct	1152 ms	464052 KB	Output is correct
24	Correct	750 ms	468948 KB	Output is correct
25	Correct	1605 ms	485792 KB	Output is correct
26	Execution timed out	2050 ms	476392 KB	Time limit exceeded
27	Execution timed out	2055 ms	487960 KB	Time limit exceeded
28	Execution timed out	2064 ms	508716 KB	Time limit exceeded
29	Execution timed out	2045 ms	506776 KB	Time limit exceeded
30	Execution timed out	2037 ms	510976 KB	Time limit exceeded
31	Execution timed out	2050 ms	473320 KB	Time limit exceeded
32	Execution timed out	2067 ms	488284 KB	Time limit exceeded