oj.uz

Submission #477542

# Submission time Handle Problem Language Result Execution time Memory
477542 2021-10-02T14:07:34 Z urosk Tracks in the Snow (BOI13_tracks) C++14
100 / 100
 759 ms 332136 KB 
//https://oj.uz/problem/view/BOI13_tracks
// __builtin_popcount(x) broj bitova
// __builtin_popcountll(x) long long
#define here cerr<<"---------------------------\n"
#include "bits/stdc++.h"
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#define ld double
#define ll long long
#define ull unsigned long long
#define llinf 100000000000000000LL // 10^17
#define iinf 2000000000 // 2*10^9
#define pb push_back
#define popb pop_back
#define fi first
#define sc second
#define endl '\n'
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pld pair<ld,ld>
#define sz(a) int(a.size())
#define all(a) a.begin(),a.end()
#define rall(a) a.begin(),a.end(),greater<int>()
#define getunique(v) {sort(all(v)); v.erase(unique(all(v)), v.end());}

using namespace std;
using namespace __gnu_pbds;

typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;

void setIO(string inoutname)
{
	freopen((inoutname+".in").c_str(),"r",stdin);
    	freopen((inoutname+".out").c_str(),"w",stdout);
}
#define mod 1
ll gcd(ll a, ll b)
{
   if(b==0) return a;
   if(a==0) return b;
   if(a>=b)  return gcd(a%b,b);
   return  gcd(a,b%a);
}
ll lcm(ll a,ll b){
   return (a/gcd(a,b))*b;
}
ll add(ll a,ll b){
	a+=b;
	a+=mod;
	if(a>=mod) a%=mod;
	return a;
}
ll mul(ll a,ll b){return(a*b)%mod;}
#define maxn 4005
ll a[maxn][maxn];
ll d[maxn][maxn];
ll n,m;
ll conv(char c){
    if(c=='.') return 0;
    if(c=='R') return 1;
    return 2;
}
bool valid(ll x,ll y){
    return (x>=1&&x<=n&&y>=1&&y<=m);
}
vector<ll> dx = {0,0,1,-1};
vector<ll> dy = {1,-1,0,0};
void tc(){
	ios_base::sync_with_stdio(false);cerr.tie(0);cout.tie(0);cin.tie(0);
    cin >> n >> m;
    for(ll i = 1;i<=n;i++){
        string s; cin >> s;
        for(ll j = 1;j<=m;j++) a[i][j] = conv(s[j-1]);
    }
    deque<pll> q;
    d[1][1] = 1;
    q.pb({1,1});
    ll ans = 0;
    while(!q.empty()){
        pll p = q.front();
        q.pop_front();
        ll x = p.fi,y = p.sc;
        ans = max(ans,d[x][y]);
        for(ll i = 0;i<4;i++){
            ll x1 = x+dx[i];
            ll y1 = y+dy[i];
            if(valid(x1,y1)==0||d[x1][y1]) continue;
            if(a[x1][y1]==0) continue;
            if(a[x][y]==a[x1][y1]){
                q.push_front({x1,y1});
                d[x1][y1] = d[x][y];
            }else{
                q.pb({x1,y1});
                d[x1][y1] = d[x][y]+1;
            }
        }
    }
    cout<<ans<<endl;
}
int main(){
	ios_base::sync_with_stdio(false);cerr.tie(0);cout.tie(0);cin.tie(0);
	//setIO("lol");
	int t; t = 1;
	while(t--){
		tc();
	}
	return 0;
}

Compilation message

tracks.cpp: In function 'void setIO(std::string)':
tracks.cpp:33:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   33 |  freopen((inoutname+".in").c_str(),"r",stdin);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
tracks.cpp:34:13: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   34 |      freopen((inoutname+".out").c_str(),"w",stdout);
      |      ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 8400 KB Output is correct
2 Correct 1 ms 464 KB Output is correct
3 Correct 1 ms 720 KB Output is correct
4 Correct 9 ms 7248 KB Output is correct
5 Correct 4 ms 3928 KB Output is correct
6 Correct 1 ms 464 KB Output is correct
7 Correct 1 ms 720 KB Output is correct
8 Correct 1 ms 848 KB Output is correct
9 Correct 1 ms 1232 KB Output is correct
10 Correct 3 ms 3152 KB Output is correct
11 Correct 3 ms 2644 KB Output is correct
12 Correct 6 ms 4176 KB Output is correct
13 Correct 4 ms 3920 KB Output is correct
14 Correct 4 ms 3920 KB Output is correct
15 Correct 13 ms 8128 KB Output is correct
16 Correct 15 ms 8408 KB Output is correct
17 Correct 13 ms 8016 KB Output is correct
18 Correct 9 ms 7248 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 31932 KB Output is correct
2 Correct 48 ms 30800 KB Output is correct
3 Correct 284 ms 201096 KB Output is correct
4 Correct 102 ms 75968 KB Output is correct
5 Correct 196 ms 141888 KB Output is correct
6 Correct 720 ms 293116 KB Output is correct
7 Correct 19 ms 33360 KB Output is correct
8 Correct 17 ms 31952 KB Output is correct
9 Correct 2 ms 1232 KB Output is correct
10 Correct 1 ms 720 KB Output is correct
11 Correct 18 ms 32708 KB Output is correct
12 Correct 2 ms 1872 KB Output is correct
13 Correct 55 ms 30732 KB Output is correct
14 Correct 30 ms 19656 KB Output is correct
15 Correct 32 ms 24904 KB Output is correct
16 Correct 22 ms 12360 KB Output is correct
17 Correct 123 ms 68156 KB Output is correct
18 Correct 124 ms 82888 KB Output is correct
19 Correct 96 ms 75976 KB Output is correct
20 Correct 64 ms 57596 KB Output is correct
21 Correct 155 ms 136264 KB Output is correct
22 Correct 189 ms 141896 KB Output is correct
23 Correct 246 ms 118344 KB Output is correct
24 Correct 150 ms 133128 KB Output is correct
25 Correct 553 ms 266880 KB Output is correct
26 Correct 628 ms 332136 KB Output is correct
27 Correct 649 ms 303412 KB Output is correct
28 Correct 738 ms 293220 KB Output is correct
29 Correct 742 ms 288696 KB Output is correct
30 Correct 759 ms 295992 KB Output is correct
31 Correct 670 ms 197264 KB Output is correct
32 Correct 618 ms 293592 KB Output is correct