Submission #124233

#	Time	Username	Problem	Language	Result	Execution time	Memory
124233		youssefbou62	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	10 / 100	2 ms	608 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 ] ;

    queue<pi> q ; 
void solve(int place , int dog ){

    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;
}
int bfs (){
    int place , dog ; 
    
    for(pi v : here[B[0]]){
        q.push( {v.fi, v.se } ) ; 
    }
    while ( !q.empty() ){
        place = q.front().fi ; 
        dog = q.front().se ;
        q.pop();  
        if( place == B[1] ){
            return dist[place] ;
        }
        solve (place , dog ) ; 
    //    cerr << place << " " << dog << " " << dist[place] << endl; 
        for( pi v : here[place] ){
            solve ( 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 << bfs ( ) << endl; 
}

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