Submission #111752

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
111752	2019-05-16T06:14:05 Z	rajarshi_basu	Tracks in the Snow (BOI13_tracks)	C++14	0 / 100	731 ms	454520 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;
	
	FOR(i,n){
	
		FOR(j,m)cin >> grid[i][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	406 ms	440824 KB	Output isn't correct
2	Incorrect	432 ms	438900 KB	Output isn't correct
3	Incorrect	392 ms	439032 KB	Output isn't correct
4	Incorrect	400 ms	440672 KB	Output isn't correct
5	Incorrect	388 ms	439836 KB	Output isn't correct
6	Incorrect	397 ms	438808 KB	Output isn't correct
7	Incorrect	353 ms	438916 KB	Output isn't correct
8	Incorrect	375 ms	438904 KB	Output isn't correct
9	Incorrect	405 ms	439320 KB	Output isn't correct
10	Incorrect	391 ms	439672 KB	Output isn't correct
11	Incorrect	376 ms	439580 KB	Output isn't correct
12	Incorrect	394 ms	439776 KB	Output isn't correct
13	Incorrect	377 ms	439888 KB	Output isn't correct
14	Incorrect	353 ms	439800 KB	Output isn't correct
15	Incorrect	403 ms	440696 KB	Output isn't correct
16	Incorrect	363 ms	440696 KB	Output isn't correct
17	Incorrect	391 ms	440640 KB	Output isn't correct
18	Incorrect	412 ms	440812 KB	Output isn't correct

Subtask #2

0 / 70.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	361 ms	453624 KB	Output isn't correct
2	Incorrect	431 ms	443580 KB	Output isn't correct
3	Incorrect	601 ms	454520 KB	Output isn't correct
4	Incorrect	452 ms	446164 KB	Output isn't correct
5	Incorrect	539 ms	450592 KB	Output isn't correct
6	Incorrect	620 ms	454468 KB	Output isn't correct
7	Incorrect	423 ms	454392 KB	Output isn't correct
8	Incorrect	426 ms	453724 KB	Output isn't correct
9	Incorrect	411 ms	438748 KB	Output isn't correct
10	Incorrect	384 ms	438904 KB	Output isn't correct
11	Incorrect	393 ms	454084 KB	Output isn't correct
12	Incorrect	353 ms	439360 KB	Output isn't correct
13	Incorrect	447 ms	443740 KB	Output isn't correct
14	Incorrect	410 ms	442256 KB	Output isn't correct
15	Incorrect	450 ms	442628 KB	Output isn't correct
16	Incorrect	390 ms	440232 KB	Output isn't correct
17	Incorrect	460 ms	446712 KB	Output isn't correct
18	Incorrect	457 ms	446524 KB	Output isn't correct
19	Incorrect	463 ms	446200 KB	Output isn't correct
20	Incorrect	405 ms	445560 KB	Output isn't correct
21	Incorrect	525 ms	450936 KB	Output isn't correct
22	Incorrect	521 ms	450500 KB	Output isn't correct
23	Incorrect	523 ms	448540 KB	Output isn't correct
24	Incorrect	562 ms	451024 KB	Output isn't correct
25	Incorrect	655 ms	454448 KB	Output isn't correct
26	Incorrect	598 ms	452528 KB	Output isn't correct
27	Incorrect	731 ms	454392 KB	Output isn't correct
28	Incorrect	616 ms	454484 KB	Output isn't correct
29	Incorrect	557 ms	454392 KB	Output isn't correct
30	Incorrect	563 ms	454136 KB	Output isn't correct
31	Incorrect	512 ms	451340 KB	Output isn't correct
32	Incorrect	632 ms	454416 KB	Output isn't correct