oj.uz

Submission #129246

# Submission time Handle Problem Language Result Execution time Memory
129246 2019-07-11T21:59:23 Z shashwatchandra Tracks in the Snow (BOI13_tracks) C++17
84.6875 / 100
 1883 ms 1048580 KB 
/*input
5 8
FFR.....
.FRRR...
.FFFFF..
..RRRFFR
.....FFF
*/
#pragma comment(linker, "/stack:200000000")
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
 
#define ll unsigned
#define int short
#define double long double
#define f first
#define s second
#define mp make_pair
#define pb push_back
 
#define RE(i,n) for (int i = 1; i <= n; i++)
#define RED(i,n) for (int i = n; i > 0; i--)
#define REPS(i,n) for(int i = 1; (i*i) <= n; i++)
#define REP(i,n) for (int i = 0; i < (int)n; i++)
#define FOR(i,a,b) for (int i = a; i < b; i++)
#define REPD(i,n) for (int i = n-1; i >= 0; i--)
#define FORD(i,a,b) for (int i = a; i >= b; i--)
 
#define all(v) v.begin(),v.end()
#define pii pair<int,int>
#define vi vector<int>
#define vvi vector<vi>
#define print(arr) for (auto it = arr.begin(); it != arr.end(); ++it) cout << *it << " "; cout << endl;
#define debug(x) cout << x << endl;
#define debug2(x,y) cout << x << " " << y << endl;
#define debug3(x,y,z) cout << x << " " << y << " " << z << endl;
 
typedef tree<
int,
null_type,
less<int>,
rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;
 

const double PI = 3.14159265358979323846264338;

int floor1(int n,int k){
    if(n%k == 0 || n >= 0)return n/k;
    return (n/k)-1;
}
 
int ceil1(int n,int k){
    return floor1(n+k-1,k);
}
 
const int N = 4001;
int a[N][N];
int lev[N][N];
int n,m;
 
pair<int,int> xd[] = {{-1,0},{0,-1},{1,0},{0,1}};
 
bool ok(int x,int y){
	return (x and y and (x <= n) and (y <= m));
}
 
queue<pair<pair<int,int>,ll > > q;
 
void dfs(int i,int j,ll para){
 
	if(lev[i][j])return;
	lev[i][j] = para;
	REP(k,4){
		int ni = i+xd[k].f;
		int nj = j+xd[k].s;
 
		if(!ok(ni,nj))continue;
		if(a[i][j] != a[ni][nj]){
			if(a[ni][nj] and !lev[ni][nj])q.push({{ni,nj},para+1});
			continue;
		}
		//lev[ni][nj] = para;
		dfs(ni,nj,para);
	}
}
 
 
void solve(){
  	cin >> n >> m;
  	RE(i,n){
  		RE(j,m){
  			char o;cin >> o;
  			//cout << o;
  			if(o == '.')continue;
  			if(o == 'F')a[i][j] = 1;
  			else a[i][j] = 2;
  		}
  	}
  	q.push({{1,1},1});
	ll ans = 1;
	while(!q.empty()){
		int i = q.front().f.f;
		int j = q.front().f.s;
		ll npara = q.front().s;
		//cout << i << " " << j << endl;
		ans = max(ans,npara);
		q.pop();
		if(lev[i][j])continue;
		dfs(i,j,npara);
	}
	cout << ans;
}
 
signed main(){
  ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  //freopen(".in","r",stdin);freopen(".out","w",stdout);
  int t = 1;
  //cin >> t;
  while(t--){
    solve();
  }
  return 0;
}

Compilation message

tracks.cpp:9:0: warning: ignoring #pragma comment  [-Wunknown-pragmas]
 #pragma comment(linker, "/stack:200000000")

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 5496 KB Output is correct
2 Correct 2 ms 504 KB Output is correct
3 Correct 2 ms 760 KB Output is correct
4 Correct 19 ms 7292 KB Output is correct
5 Correct 8 ms 2936 KB Output is correct
6 Correct 2 ms 504 KB Output is correct
7 Correct 2 ms 760 KB Output is correct
8 Correct 3 ms 888 KB Output is correct
9 Correct 3 ms 1144 KB Output is correct
10 Correct 7 ms 2552 KB Output is correct
11 Correct 7 ms 2936 KB Output is correct
12 Correct 13 ms 3192 KB Output is correct
13 Correct 7 ms 2936 KB Output is correct
14 Correct 7 ms 2936 KB Output is correct
15 Correct 25 ms 5260 KB Output is correct
16 Correct 30 ms 5496 KB Output is correct
17 Correct 20 ms 5244 KB Output is correct
18 Correct 18 ms 7288 KB Output is correct

Subtask #2
54.6875 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 31608 KB Output is correct
2 Correct 95 ms 14032 KB Output is correct
3 Runtime error 1266 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
4 Correct 146 ms 29528 KB Output is correct
5 Correct 363 ms 39416 KB Output is correct
6 Correct 1415 ms 193208 KB Output is correct
7 Correct 34 ms 32888 KB Output is correct
8 Correct 33 ms 31480 KB Output is correct
9 Correct 5 ms 1144 KB Output is correct
10 Correct 3 ms 760 KB Output is correct
11 Correct 33 ms 32328 KB Output is correct
12 Correct 4 ms 1656 KB Output is correct
13 Correct 93 ms 13972 KB Output is correct
14 Correct 55 ms 9848 KB Output is correct
15 Correct 47 ms 12408 KB Output is correct
16 Correct 44 ms 5368 KB Output is correct
17 Correct 222 ms 25512 KB Output is correct
18 Runtime error 990 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
19 Correct 169 ms 29560 KB Output is correct
20 Runtime error 1086 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
21 Runtime error 1151 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
22 Correct 314 ms 39548 KB Output is correct
23 Correct 446 ms 35960 KB Output is correct
24 Runtime error 1202 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
25 Runtime error 1283 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
26 Runtime error 1403 ms 1048576 KB Execution killed with signal 9 (could be triggered by violating memory limits)
27 Correct 1660 ms 609804 KB Output is correct
28 Correct 1447 ms 193300 KB Output is correct
29 Correct 1382 ms 200352 KB Output is correct
30 Correct 1516 ms 321456 KB Output is correct
31 Correct 1076 ms 52424 KB Output is correct
32 Correct 1883 ms 617604 KB Output is correct