oj.uz

Submission #975101

# Submission time Handle Problem Language Result Execution time Memory
975101 2024-05-04T12:44:47 Z Adarsh Tracks in the Snow (BOI13_tracks) C++14
100 / 100
 748 ms 338136 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define F first
#define S second
#define INF 10000
int mod = 1e9+7;
typedef pair<int, int> pii;
typedef pair<long, long> pll;


int n,m;
int dx[] = {1,0,-1,0};
int dy[] = {0,1,0,-1};
string s[4040];

bool check(int x, int y){
    if(x<0 || x>=n || y<0 || y>=m || s[x][y]=='.'){
        return 0;
    }
    return 1;
}

void solve(){
   cin>>n>>m;
   for(int i=0;i<n;i++){
    cin>>s[i];
   }

   vector<vector<int>> dis;
   vector<vector<int>> vis;
   dis = vector<vector<int>>(n+1,vector<int>(m+1,1e18));
   vis = vector<vector<int>>(n+1,vector<int>(m+1,0));

   dis[0][0] = 1;
   deque<pair<int,int>> dq;
   dq.push_back({0,0});

   while(!dq.empty()){
     auto cur = dq.front();
     dq.pop_front();
    
     if(vis[cur.F][cur.S]){
        continue;
     }else{
        vis[cur.F][cur.S] = 1;
     }
     
     for(int i=0;i<4;i++){
        int nx = cur.F+dx[i];
        int ny = cur.S+dy[i];

        
        if(check(nx,ny)){
            int weight;
            if(s[nx][ny]==s[cur.F][cur.S]){
                weight = 0;
            }else{
                weight = 1;
            }

            if(dis[nx][ny]>dis[cur.F][cur.S]+weight){
                dis[nx][ny]=dis[cur.F][cur.S]+weight;
                if(weight){
                    dq.push_back({nx,ny});
                }else{
                    dq.push_front({nx,ny});
                }
            }
        }
     }

   }

   int ans = 1;

   for(int i=0;i<n;i++){
    for(int j=0;j<m;j++){
        if(vis[i][j]){
            ans = max(ans,dis[i][j]);
        }
    }
   }
cout<<ans<<endl;
    
}


signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t=1;
    //cin>>t;
    while(t--){
        solve();
    }
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 4956 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 5 ms 3676 KB Output is correct
5 Correct 2 ms 1880 KB Output is correct
6 Correct 1 ms 412 KB Output is correct
7 Correct 0 ms 600 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 2 ms 1884 KB Output is correct
11 Correct 2 ms 1372 KB Output is correct
12 Correct 4 ms 2140 KB Output is correct
13 Correct 3 ms 1884 KB Output is correct
14 Correct 2 ms 2096 KB Output is correct
15 Correct 9 ms 4952 KB Output is correct
16 Correct 11 ms 4956 KB Output is correct
17 Correct 7 ms 4864 KB Output is correct
18 Correct 5 ms 3676 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1628 KB Output is correct
2 Correct 38 ms 27836 KB Output is correct
3 Correct 233 ms 277364 KB Output is correct
4 Correct 78 ms 65676 KB Output is correct
5 Correct 170 ms 155984 KB Output is correct
6 Correct 736 ms 305192 KB Output is correct
7 Correct 2 ms 1628 KB Output is correct
8 Correct 2 ms 1616 KB Output is correct
9 Correct 2 ms 1628 KB Output is correct
10 Correct 1 ms 1116 KB Output is correct
11 Correct 1 ms 1628 KB Output is correct
12 Correct 1 ms 860 KB Output is correct
13 Correct 37 ms 27992 KB Output is correct
14 Correct 20 ms 16476 KB Output is correct
15 Correct 20 ms 18012 KB Output is correct
16 Correct 18 ms 11868 KB Output is correct
17 Correct 110 ms 70884 KB Output is correct
18 Correct 96 ms 69972 KB Output is correct
19 Correct 77 ms 65472 KB Output is correct
20 Correct 55 ms 60240 KB Output is correct
21 Correct 141 ms 161592 KB Output is correct
22 Correct 162 ms 156108 KB Output is correct
23 Correct 195 ms 134484 KB Output is correct
24 Correct 134 ms 157592 KB Output is correct
25 Correct 632 ms 269148 KB Output is correct
26 Correct 388 ms 307316 KB Output is correct
27 Correct 556 ms 338136 KB Output is correct
28 Correct 748 ms 297092 KB Output is correct
29 Correct 733 ms 292336 KB Output is correct
30 Correct 663 ms 301808 KB Output is correct
31 Correct 469 ms 173488 KB Output is correct
32 Correct 556 ms 317716 KB Output is correct