oj.uz

Submission #1093376

# Submission time Handle Problem Language Result Execution time Memory
1093376 2024-09-26T18:00:30 Z JuanJL Jetpack (COCI16_jetpack) C++17
80 / 80
 27 ms 16412 KB 
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 10;
const int MAXM = 100000+5;

#define fst first
#define snd second
#define pb push_back
#define SZ(x) (int)x.size()
#define ALL(x) x.begin(),x.end()
#define forn(i,a,b) for(int i = a; i < b; i++)
#define mset(a,v) memset(a,v,sizeof(a))

typedef int ll;

//vector<pair<ll,ll>> adj[MAXN][MAXM];
bool visited[MAXN][MAXM];
pair<ll,ll> parent[MAXN][MAXM];
string table[MAXN];
ll n=10, m; 

void dfs(ll y, ll x, ll py, ll px){
    if(visited[y][x]) return;
    visited[y][x]=true;
    parent[y][x]={py,px};
    if(y==n-1 && x+1<m && table[y][x+1]=='.') dfs(y,x+1,y,x);
    if(y+1<10 && x+1<m && table[y+1][x+1]=='.') dfs(y+1,x+1,y,x);
    if(y-1>=0 && x+1<m && table[y-1][x+1]=='.') dfs(y-1,x+1,y,x);
    if(y==0 && x+1<m && table[y][x+1]=='.') dfs(y,x+1,y,x);
}

int main(){
    mset(visited,false);
    cin>>m;

    for(int i = n-1; i >= 0; i--){
            cin>>table[i];
    }

    /*forn(i,0,n){
        forn(j,0,m){
            if(i==n-1 && j+1<m && table[i][j+1]=='.') adj[i][j].pb({i,j+1});
            if(i+1<10 && j+1<m && table[i+1][j+1]=='.') adj[i][j].pb({i+1,j+1});
            if(i-1>=0 && j+1<m && table[i-1][j+1]=='.') adj[i][j].pb({i-1,j+1});
            if(i==0 && j+1<m && table[i][j+1]=='.') adj[i][j].pb({i,j+1});
        }
    }*/

    //cout<<"paso\n";

    dfs(0,0,0,0);

    ll fila;
    forn(i,0,n){
        if(visited[i][m-1]){
            fila=i;
        }
    }


    vector<pair<ll,ll>> res;
    bool sube = false;
    ll aux = 0;
    pair<ll,ll> ndAct = {fila,m-1};
    while(ndAct.snd!=0){
        //cout<<ndAct.fst<<" "<<ndAct.snd<<'\n';
        if((parent[ndAct.fst][ndAct.snd].fst<ndAct.fst)||(parent[ndAct.fst][ndAct.snd].fst==ndAct.fst && ndAct.fst==n-1)){
            sube=true;
            aux++;
        }else if(sube){
            res.pb({ndAct.snd,aux});
            sube=false;
            aux=0;
        }
        ndAct=parent[ndAct.fst][ndAct.snd];
    }
    //cout<<ndAct.fst<<" "<<ndAct.snd<<'\n';
    if(sube) res.pb({0,aux});

    reverse(ALL(res));
    cout<<SZ(res)<<'\n';
    for(auto i:res){
        cout<<i.fst<<" "<<i.snd<<'\n';
    }

    return 0;
}

Compilation message

jetpack.cpp: In function 'int main()':
jetpack.cpp:69:103: warning: 'fila' may be used uninitialized in this function [-Wmaybe-uninitialized]
   69 |         if((parent[ndAct.fst][ndAct.snd].fst<ndAct.fst)||(parent[ndAct.fst][ndAct.snd].fst==ndAct.fst && ndAct.fst==n-1)){
      |                                                          ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~

Subtask #1
80.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1372 KB Output is correct
2 Correct 1 ms 1480 KB Output is correct
3 Correct 1 ms 1372 KB Output is correct
4 Correct 1 ms 1628 KB Output is correct
5 Correct 2 ms 2140 KB Output is correct
6 Correct 4 ms 2464 KB Output is correct
7 Correct 6 ms 4404 KB Output is correct
8 Correct 14 ms 8972 KB Output is correct
9 Correct 20 ms 12680 KB Output is correct
10 Correct 27 ms 16412 KB Output is correct