oj.uz

Submission #1084180

# Submission time Handle Problem Language Result Execution time Memory
1084180 2024-09-05T14:31:28 Z fonikos01 Tracks in the Snow (BOI13_tracks) C++14
100 / 100
 597 ms 222124 KB 
#include <bits/stdc++.h>
#include <vector>
#include <tuple>
// #include "debugging.h"
// #include <atcoder/lazysegtree>
// #include <atcoder/modint>
// #include <atcoder/dsu>

// #include <atcoder/segtree>
// using namespace atcoder;
// using mint = modint998244353;

using namespace std;
const int LARGE = 1e9;

#define all(x) (x).begin(), (x).end()

using ll = long long;
typedef pair<ll, ll> pi;

// bool cmp(pair<ll, ll> a, pair<ll, ll> b)
// {
//         if (a.second < b.second)
//                 return true;
//         return false;
// }
// struct node
// {
//         // part which will store data
//         int data;
//         // pointer to the previous node
//         struct node *prev;
//         // pointer to the next node
//         struct node *next;
// };
const int MOD = 1e9+7;
template<int MOD, int RT> struct mint {
	static const int mod = MOD;
	static constexpr mint rt() { return RT; } // primitive root
 	int v; 
 	explicit operator int() const { return v; } 
	mint():v(0) {}
	mint(ll _v):v(int(_v%MOD)) { v += (v<0)*MOD; }
	mint& operator+=(mint o) { 
		if ((v += o.v) >= MOD) v -= MOD; 
		return *this; }
	mint& operator-=(mint o) { 
		if ((v -= o.v) < 0) v += MOD; 
		return *this; }
	mint& operator*=(mint o) { 
		v = int((ll)v*o.v%MOD); return *this; }
	friend mint pow(mint a, ll p) { assert(p >= 0);
		return p==0?1:pow(a*a,p/2)*(p&1?a:1); }
	friend mint inv(mint a) { assert(a.v != 0); return pow(a,MOD-2); }
	friend mint operator+(mint a, mint b) { return a += b; }
	friend mint operator-(mint a, mint b) { return a -= b; }
	friend mint operator*(mint a, mint b) { return a *= b; }
};
using mi = mint<(int)MOD, 5>;

mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());

ll solve()
{
	ll H, W; cin >> H >> W;

	vector<string> A(H);
	for (int i = 0; i < H; i++) cin >> A[i];

	vector<vector<ll>> vis(H, vector<ll>(W));
	vis[0][0] = 1;
	char curr = A[0][0];
	deque<pair<ll,ll>> dq;
	dq.push_front(make_pair(0,0));
	vector<pair<ll,ll>> ut1 = {{0, 1}, {0, -1}, {1, 0}, {-1, 0},};
	ll ans = 1;

	while(!dq.empty()) {
		pair<ll,ll> temp = dq.front();
		dq.pop_front();
		ll i = temp.first, j = temp.second;
		if (A[i][j] != curr) {
			curr = A[i][j];
			ans++;
		}
		for (pair<ll,ll> utp : ut1) {
			ll newI = utp.first+i, newJ = utp.second+j;
			if (newI < 0 || newI >= H || newJ < 0 || newJ >= W || vis[newI][newJ] || A[newI][newJ] == '.') continue;
			vis[newI][newJ] = 1;
			if (A[newI][newJ] == curr) dq.push_front(make_pair(newI, newJ));
			else dq.push_back(make_pair(newI, newJ));
		}
	} 

	cout << ans << '\n';

	return 0;
}

int main()
{
        ios::sync_with_stdio(false);
        cin.tie(nullptr);
        // freopen("248.in", "r", stdin);
        // freopen("248.out", "w", stdout);

        // ll caseCnt = 1;


        // ll T;
        // cin >> T;
        // while (T--)
        // {
                
                solve();

                // 	cout << "Case #"<< caseCnt << ": " << ans << '\n';
                // 	caseCnt++;
        // }

        return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 3160 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 5 ms 2392 KB Output is correct
5 Correct 1 ms 1116 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 536 KB Output is correct
9 Correct 1 ms 444 KB Output is correct
10 Correct 2 ms 996 KB Output is correct
11 Correct 1 ms 860 KB Output is correct
12 Correct 3 ms 1340 KB Output is correct
13 Correct 2 ms 1116 KB Output is correct
14 Correct 1 ms 1116 KB Output is correct
15 Correct 10 ms 2908 KB Output is correct
16 Correct 9 ms 2908 KB Output is correct
17 Correct 6 ms 2652 KB Output is correct
18 Correct 5 ms 2304 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1116 KB Output is correct
2 Correct 33 ms 15964 KB Output is correct
3 Correct 172 ms 159248 KB Output is correct
4 Correct 56 ms 37492 KB Output is correct
5 Correct 91 ms 89428 KB Output is correct
6 Correct 591 ms 185808 KB Output is correct
7 Correct 2 ms 860 KB Output is correct
8 Correct 1 ms 1116 KB Output is correct
9 Correct 1 ms 860 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 1 ms 1116 KB Output is correct
12 Correct 1 ms 604 KB Output is correct
13 Correct 29 ms 15956 KB Output is correct
14 Correct 15 ms 9412 KB Output is correct
15 Correct 11 ms 10332 KB Output is correct
16 Correct 13 ms 6848 KB Output is correct
17 Correct 84 ms 40532 KB Output is correct
18 Correct 58 ms 40048 KB Output is correct
19 Correct 58 ms 37540 KB Output is correct
20 Correct 39 ms 34396 KB Output is correct
21 Correct 102 ms 92696 KB Output is correct
22 Correct 85 ms 89712 KB Output is correct
23 Correct 177 ms 77136 KB Output is correct
24 Correct 96 ms 90460 KB Output is correct
25 Correct 273 ms 159064 KB Output is correct
26 Correct 590 ms 222124 KB Output is correct
27 Correct 554 ms 195636 KB Output is correct
28 Correct 597 ms 185800 KB Output is correct
29 Correct 587 ms 180916 KB Output is correct
30 Correct 581 ms 190272 KB Output is correct
31 Correct 355 ms 102852 KB Output is correct
32 Correct 535 ms 192840 KB Output is correct