Submission #111751

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
111751	2019-05-16T06:12:53 Z	rajarshi_basu	Tracks in the Snow (BOI13_tracks)	C++14	0 / 100	499 ms	470056 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});
		}
	}
	*/
	

	//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

0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	416 ms	440952 KB	Output isn't correct
2	Incorrect	391 ms	438840 KB	Output isn't correct
3	Incorrect	428 ms	438872 KB	Output isn't correct
4	Incorrect	400 ms	440776 KB	Output isn't correct
5	Incorrect	387 ms	439952 KB	Output isn't correct
6	Incorrect	406 ms	438780 KB	Output isn't correct
7	Incorrect	400 ms	439020 KB	Output isn't correct
8	Incorrect	398 ms	439032 KB	Output isn't correct
9	Incorrect	388 ms	439288 KB	Output isn't correct
10	Incorrect	410 ms	439800 KB	Output isn't correct
11	Incorrect	399 ms	439544 KB	Output isn't correct
12	Incorrect	397 ms	439928 KB	Output isn't correct
13	Incorrect	415 ms	439936 KB	Output isn't correct
14	Incorrect	400 ms	439952 KB	Output isn't correct
15	Incorrect	395 ms	440936 KB	Output isn't correct
16	Incorrect	397 ms	440952 KB	Output isn't correct
17	Incorrect	402 ms	440952 KB	Output isn't correct
18	Incorrect	398 ms	440796 KB	Output isn't correct

Subtask #2

0 / 70.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	387 ms	453760 KB	Output isn't correct
2	Incorrect	413 ms	444116 KB	Output isn't correct
3	Incorrect	457 ms	454712 KB	Output isn't correct
4	Incorrect	401 ms	446532 KB	Output isn't correct
5	Incorrect	427 ms	450808 KB	Output isn't correct
6	Incorrect	484 ms	470056 KB	Output isn't correct
7	Incorrect	444 ms	454372 KB	Output isn't correct
8	Incorrect	382 ms	453752 KB	Output isn't correct
9	Incorrect	392 ms	438968 KB	Output isn't correct
10	Incorrect	398 ms	438804 KB	Output isn't correct
11	Incorrect	399 ms	454176 KB	Output isn't correct
12	Incorrect	386 ms	439288 KB	Output isn't correct
13	Incorrect	414 ms	443896 KB	Output isn't correct
14	Incorrect	429 ms	442572 KB	Output isn't correct
15	Incorrect	382 ms	442972 KB	Output isn't correct
16	Incorrect	383 ms	440568 KB	Output isn't correct
17	Incorrect	417 ms	447036 KB	Output isn't correct
18	Incorrect	481 ms	446948 KB	Output isn't correct
19	Incorrect	434 ms	446456 KB	Output isn't correct
20	Incorrect	451 ms	445816 KB	Output isn't correct
21	Incorrect	400 ms	451040 KB	Output isn't correct
22	Incorrect	404 ms	450808 KB	Output isn't correct
23	Incorrect	423 ms	448792 KB	Output isn't correct
24	Incorrect	430 ms	451172 KB	Output isn't correct
25	Incorrect	499 ms	454604 KB	Output isn't correct
26	Incorrect	424 ms	452600 KB	Output isn't correct
27	Incorrect	415 ms	454520 KB	Output isn't correct
28	Incorrect	411 ms	454648 KB	Output isn't correct
29	Incorrect	490 ms	454392 KB	Output isn't correct
30	Incorrect	429 ms	454136 KB	Output isn't correct
31	Incorrect	443 ms	451416 KB	Output isn't correct
32	Incorrect	442 ms	454520 KB	Output isn't correct