Submission #124211

#	Time	Username	Problem	Language	Result	Execution time	Memory
124211		youssefbou62	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	10 / 100	18 ms	1532 KiB

skyscraper

#include  <bits/stdc++.h>

using namespace std;

#define mp make_pair
#define fi first
#define se second
#define all(v) v.begin(),v.end()
#define allarr(a) a , a + n
#define ll long long
#define ull unsigned long long 
#define pb push_back
#define fastio ios_base::sync_with_stdio(false) ; cin.tie(NULL); cout.tie(NULL)
typedef pair<int, int> pi;
typedef pair<ll,ll> pll; 
typedef pair<int,pi> trp ;
typedef vector<pi> vpi;
typedef vector<pll> vpll ;
ll ab (ll x ) { return (x>0?x:-x); }
const int N = 3005 ; 
int P[N] , B[N] ; 
int dist[N] , n , m ; 
vpi  here [N] ;
bool visited[ N ][ N ] ; 
int solve (){
    queue<pi> q ; 
    int place , dog ; 
    
    q.push({B[0],0}) ; 

    while ( !q.empty() ){
        place = q.front().fi ; 
        dog = q.front().se ;
        q.pop();  
        if( place == B[1] ){
            return dist[place] ; 
        }
    //    cerr << place << " " << dog << " " << dist[place] << endl; 
        visited[place][P[dog]] = 1 ; 
        int plus = place + P[dog] , minus = place - P[dog] ; 
        if( plus < n && !visited[plus][P[dog]])
            q.push( { plus , dog } ) , dist[plus] = dist[place]+1 ;
        if( minus >= 0 && !visited[minus][P[dog]])
            q.push( { minus , dog } ) , dist[minus] = dist[place] + 1 ; 
        for( pi v : here[place] ){
            // cout << v.fi << " " << v.se << endl;
            if( !visited[v.fi][P[v.se]] )
                q.push( {v.fi , v.se } ) ; 
        }
    }
    return -1 ; 
}

void input(){
    // ifstream cin ("in.in") ; 
    cin >> n >> m ; 
    for(int i = 0 ; i < m  ; i++ ){
        cin >> B[i] >> P[i] ; 
        here[B[i]].pb({B[i] , i}) ; 
    }
}
int main(){
    input() ; 
    cout << solve ( ) << endl; 
}

• Subtask 1: 10 / 10
• Subtask 2: 0 / 12
• Subtask 3: 0 / 14
• Subtask 4: 0 / 21
• Subtask 5: 0 / 43