Submission #738765

#TimeUsernameProblemLanguageResultExecution timeMemory
738765airthsTracks in the Snow (BOI13_tracks)C++17
91.25 / 100
2090 ms401956 KiB
/* * * ^v^ * */ #include <iostream> #include <string> #include <cmath> #include <vector> #include <iomanip> #include <map> #include <numeric> #include <functional> #include <algorithm> #include <set> #include <queue> #include <deque> #include <climits> #include <cstdlib> #include <chrono> // #include <ext/pb_ds/assoc_container.hpp> // #include <ext/pb_ds/tree_policy.hpp> // using namespace __gnu_pbds; using namespace std; // #define ordered_set tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> #define iamtefu ios_base::sync_with_stdio(false); cin.tie(0); #define ll int #define ld long double #define sc(a) scanf("%lld", &a); #define scv(a, n) vector<ll> a(n);fl(i,0,n){sc(a[i])} #define prl(a) fl(i,0,a.size()){printf("%lld ", a[i]);}printf("\n"); #define fl(i,a,n) for (ll i(a); i<n; i++) #define rfl(i,a,n) for (ll i(n-1); i>=a; i--) #define print(a) for (auto x:a){cout<<x<<" ";} cout<<"\n"; #define tt int tt; cin>>tt; for(;tt--;) ll gcd(ll a, ll b){ if (b==0){ return a; } return gcd(b, a%b); } ll pw(ll a, ll b, ll m){ ll res=1; a%=m; while (b){ if (b&1){ res=(res*a)%m; } a=(a*a)%m; b/=2; } return res; } void scn(){ ll n, m; cin>>n>>m; vector <string> a(n+1); fl(i,0,n){ cin>>a[i]; } vector <ll> di={1, 1, 0, -1, -1, -1, 0, 1}; vector <ll> dj={0, 1, 1, 1, 0, -1, -1, -1}; vector <vector <ll>> dis(n, vector <ll>(m, 0)); dis[0][0] = 1; ll ans = 0; deque <vector <ll>> q; q.push_back({0, 0, 0}); while (!q.empty()){ auto j = q.front(); q.pop_front(); ans = max(ans, dis[j[1]][j[2]]); // cerr<<j[1]<<" "<<j[2]<<'\n'; for (int d = 0; d<8; d+=2){ ll i1 = j[1]+di[d], j1 = j[2]+dj[d]; if (i1<0 || i1>=n || j1<0 || j1>=m || a[i1][j1]=='.' || dis[i1][j1]){ continue; } else { dis[i1][j1] = dis[j[1]][j[2]]+(a[j[1]][j[2]]!=a[i1][j1]); if (a[j[1]][j[2]]==a[i1][j1]){ q.push_front({-dis[i1][j1], i1, j1}); } else { q.push_back({-dis[i1][j1], i1, j1}); } } } } cout<<ans<<'\n'; // not necessarily distinct } int main(){ iamtefu; #if defined(airths) auto t1=chrono::high_resolution_clock::now(); freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); #else // #endif // tt { scn(); } #if defined(airths) auto t2=chrono::high_resolution_clock::now(); ld ti=chrono::duration_cast<chrono::nanoseconds>(t2-t1).count(); ti*=1e-6; cerr<<"Time: "<<setprecision(12)<<ti; cerr<<"ms\n"; #endif return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...