Submission #1090698

#	Time	Username	Problem	Language	Result	Execution time	Memory
1090698		vjudge1	Jetpack (COCI16_jetpack)	C++17	56 / 80	54 ms	65536 KiB

jetpack

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 10;
const int MAXM = 200000+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];

void dfs(ll x, ll y){
    if(visited[x][y]) return;
    visited[x][y]=true;
    //cout<<x<<" "<<y<<'\n';    
    for(auto nd:adj[x][y]) if(!visited[nd.fst][nd.snd]){
        parent[nd.fst][nd.snd]={x,y};
        dfs(nd.fst,nd.snd);
    }
}

int main(){
    mset(visited,false);
    ll n,m; n=10;
    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);

    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 (stderr)

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: 56 / 80