oj.uz

Submission #975100

# Submission time Handle Problem Language Result Execution time Memory
975100 2024-05-04T12:42:14 Z Adarsh Tracks in the Snow (BOI13_tracks) C++14
0 / 100
 769 ms 353816 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});
                }
            }
        }
     }

   }

   cout<<dis[n-1][m-1]+1<<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
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 4956 KB Output isn't correct
2 Incorrect 1 ms 344 KB Output isn't correct
3 Incorrect 1 ms 604 KB Output isn't correct
4 Incorrect 5 ms 3640 KB Output isn't correct
5 Incorrect 2 ms 1880 KB Output isn't correct
6 Incorrect 1 ms 348 KB Output isn't correct
7 Incorrect 1 ms 600 KB Output isn't correct
8 Incorrect 1 ms 604 KB Output isn't correct
9 Incorrect 0 ms 604 KB Output isn't correct
10 Incorrect 2 ms 1624 KB Output isn't correct
11 Incorrect 2 ms 1372 KB Output isn't correct
12 Incorrect 4 ms 2216 KB Output isn't correct
13 Incorrect 2 ms 1884 KB Output isn't correct
14 Incorrect 2 ms 1884 KB Output isn't correct
15 Incorrect 8 ms 4956 KB Output isn't correct
16 Incorrect 10 ms 4956 KB Output isn't correct
17 Incorrect 7 ms 4700 KB Output isn't correct
18 Incorrect 5 ms 3676 KB Output isn't correct

Subtask #2
0 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 1528 KB Output isn't correct
2 Incorrect 37 ms 28200 KB Output isn't correct
3 Incorrect 251 ms 284556 KB Output isn't correct
4 Incorrect 67 ms 67088 KB Output isn't correct
5 Incorrect 156 ms 160084 KB Output isn't correct
6 Incorrect 727 ms 312672 KB Output isn't correct
7 Incorrect 2 ms 1624 KB Output isn't correct
8 Incorrect 2 ms 1628 KB Output isn't correct
9 Incorrect 2 ms 1628 KB Output isn't correct
10 Incorrect 1 ms 1116 KB Output isn't correct
11 Incorrect 1 ms 1628 KB Output isn't correct
12 Incorrect 1 ms 856 KB Output isn't correct
13 Incorrect 36 ms 28228 KB Output isn't correct
14 Incorrect 20 ms 16476 KB Output isn't correct
15 Incorrect 18 ms 18268 KB Output isn't correct
16 Incorrect 17 ms 11868 KB Output isn't correct
17 Incorrect 94 ms 72548 KB Output isn't correct
18 Incorrect 88 ms 71508 KB Output isn't correct
19 Incorrect 68 ms 67084 KB Output isn't correct
20 Incorrect 52 ms 61524 KB Output isn't correct
21 Incorrect 139 ms 165704 KB Output isn't correct
22 Incorrect 161 ms 160280 KB Output isn't correct
23 Incorrect 194 ms 138064 KB Output isn't correct
24 Incorrect 139 ms 161692 KB Output isn't correct
25 Incorrect 661 ms 284760 KB Output isn't correct
26 Incorrect 402 ms 318556 KB Output isn't correct
27 Incorrect 544 ms 353816 KB Output isn't correct
28 Incorrect 769 ms 312552 KB Output isn't correct
29 Incorrect 693 ms 307836 KB Output isn't correct
30 Incorrect 616 ms 317220 KB Output isn't correct
31 Incorrect 459 ms 183148 KB Output isn't correct
32 Incorrect 506 ms 333652 KB Output isn't correct