oj.uz

Submission #1090685

# Submission time Handle Problem Language Result Execution time Memory
1090685 2024-09-18T15:25:53 Z vjudge1 Jetpack (COCI16_jetpack) C++17
56 / 80
 51 ms 65536 KB 
#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 long long 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

jetpack.cpp: In function 'int main()':
jetpack.cpp:69:56: 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.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 49240 KB Output is correct
2 Correct 14 ms 49244 KB Output is correct
3 Correct 13 ms 49372 KB Output is correct
4 Correct 14 ms 50024 KB Output is correct
5 Correct 17 ms 52196 KB Output is correct
6 Correct 21 ms 53584 KB Output is correct
7 Correct 40 ms 61520 KB Output is correct
8 Runtime error 44 ms 65536 KB Execution killed with signal 9
9 Runtime error 46 ms 65536 KB Execution killed with signal 9
10 Runtime error 51 ms 65536 KB Execution killed with signal 9