oj.uz

답안 #649071

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
649071 2022-10-09T07:01:01 Z rickbaishuak Tracks in the Snow (BOI13_tracks) C++14
82.5 / 100
 2000 ms 1048576 KB 
#include <bits/stdc++.h>
#define pb push_back
#define er erase
#define in insert
#define s(a, x, y) sort(a.begin()+x, a.begin()+y);
#define r(a, x, y) reverse(a.begin()+x, a.begin()+y);
#define mp make_pair
#define F first
#define S second
#define ll long long
#define ld long double
#define forn(i, a, b) for(int i=a; i<=b; i++)
#define form(i, a, b) for(int i=a; i>=b; i--)
#define PI 3.14159265358979
#define inf 2147483647
#define sp setprecision
#define pii pair <int, int>
#define gcd __gcd
#define endl '\n'
#define sz(a) (int)a.size()
using namespace std;
const ll N = 4000 + 13;
ll t1, n, m, d[N][N], ans;
vector <pii> g[N][N];
string t;
char s[N][N];
deque <pii> q;
bool st1[N][N], st2[N][N];
pii v;
void solve(){
	cin >> n >> m;
	forn (i, 1, n){
		cin >> t;
		forn (j, 1, m){
			s[i][j] = t[j - 1];
			if (i > 1 && s[i][j] != '.' && s[i - 1][j] != '.') {
				g[i][j].pb ({i - 1, j});
				g[i - 1][j].pb ({i, j});
				if (s[i][j] == s[i - 1][j]) st2[i][j] = 0;
				else st2[i][j] = 1;
			}
			if (j > 1 && s[i][j] != '.' && s[i][j - 1] != '.') {
				g[i][j].pb ({i, j - 1});
				g[i][j - 1].pb ({i, j});
				if (s[i][j] == s[i][j - 1]) st1[i][j] = 0;
				else st1[i][j] = 1;
			}
		}
	}
	q.push_back ({1, 1});
	d[1][1] = 1;
	while (q.size()){
		v = q[0];
		q.pop_front();
		for (pii to: g[v.F][v.S]){
			if (!d[to.F][to.S]){
				d[to.F][to.S] = d[v.F][v.S];
				if (v.F == to.F && !st1[v.F][max (v.S, to.S)] || v.S == to.S && !st2[max (v.F, to.F)][v.S]) q.push_front (to);
				else {
					q.push_back (to);
					d[to.F][to.S] ++;
				}
				ans = max (ans, d[to.F][to.S]);
			}
		}
	}
//	forn (i, 1, n){
//		forn (j, 1, m){
//			cout << d[i][j];
//		}
//		cout << endl;
//	}
	cout << ans << endl;
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
//	cin >> t1;
	t1 = 1;
	while (t1 --){
		solve();
	}
	return 0;
}
/*
5
0.50 0.29 0.49 0.95 0.66
2 3
0 3
3 4
2 1

5
0.50 0.29 0.49 0.95 0.83
2 3
0 3
3 4
2 1
1
4 0.66
*/

Compilation message

tracks.cpp: In function 'void solve()':
tracks.cpp:58:21: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   58 |     if (v.F == to.F && !st1[v.F][max (v.S, to.S)] || v.S == to.S && !st2[max (v.F, to.F)][v.S]) q.push_front (to);
      |         ~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 223 ms 399340 KB Output is correct
2 Correct 168 ms 378700 KB Output is correct
3 Correct 170 ms 379320 KB Output is correct
4 Correct 204 ms 394944 KB Output is correct
5 Correct 179 ms 384508 KB Output is correct
6 Correct 174 ms 378764 KB Output is correct
7 Correct 180 ms 379328 KB Output is correct
8 Correct 179 ms 379644 KB Output is correct
9 Correct 174 ms 380108 KB Output is correct
10 Correct 177 ms 383940 KB Output is correct
11 Correct 183 ms 383948 KB Output is correct
12 Correct 192 ms 387704 KB Output is correct
13 Correct 181 ms 384440 KB Output is correct
14 Correct 182 ms 384364 KB Output is correct
15 Correct 215 ms 396400 KB Output is correct
16 Correct 221 ms 399488 KB Output is correct
17 Correct 199 ms 392508 KB Output is correct
18 Correct 305 ms 394996 KB Output is correct

Subtask #2
52.5 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Correct 204 ms 429092 KB Output is correct
2 Correct 313 ms 434728 KB Output is correct
3 Correct 869 ms 653492 KB Output is correct
4 Correct 406 ms 459952 KB Output is correct
5 Correct 679 ms 612520 KB Output is correct
6 Runtime error 1646 ms 1048576 KB Execution killed with signal 9
7 Correct 205 ms 431180 KB Output is correct
8 Correct 207 ms 429028 KB Output is correct
9 Correct 189 ms 380400 KB Output is correct
10 Correct 181 ms 379132 KB Output is correct
11 Correct 201 ms 426904 KB Output is correct
12 Correct 181 ms 381000 KB Output is correct
13 Correct 322 ms 434504 KB Output is correct
14 Correct 262 ms 414356 KB Output is correct
15 Correct 255 ms 408316 KB Output is correct
16 Correct 248 ms 404392 KB Output is correct
17 Correct 514 ms 501720 KB Output is correct
18 Correct 451 ms 472168 KB Output is correct
19 Correct 378 ms 460172 KB Output is correct
20 Correct 337 ms 458320 KB Output is correct
21 Correct 579 ms 552764 KB Output is correct
22 Correct 685 ms 608532 KB Output is correct
23 Correct 860 ms 593956 KB Output is correct
24 Correct 561 ms 549276 KB Output is correct
25 Correct 1736 ms 683316 KB Output is correct
26 Runtime error 1547 ms 1048576 KB Execution killed with signal 9
27 Runtime error 1681 ms 1048576 KB Execution killed with signal 9
28 Runtime error 1673 ms 1048576 KB Execution killed with signal 9
29 Runtime error 1594 ms 1048576 KB Execution killed with signal 9
30 Runtime error 1639 ms 1048576 KB Execution killed with signal 9
31 Execution timed out 2145 ms 959400 KB Time limit exceeded
32 Runtime error 1620 ms 1048576 KB Execution killed with signal 9