Submission #124238

#	Time	Username	Problem	Language	Result	Execution time	Memory
124238		youssefbou62	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	10 / 100	704 ms	262148 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;
vector<int> here[N];
bool visited[N][N];

queue<vector<int>> q;
void push ( int i , int j , int d ){
    if( i < n && i >= 0 && !visited[i][P[j]])
            q.push({i, j , d + 1 }) ; 
}
int bfs()
{
    int place, dog;
    q.push({B[0],0,0}); 
    for( int v : here[B[0]] ){
        push ( B[0],v,-1 ) ; 
        push ( B[0], v , -1  ) ;  
    }
    while (!q.empty())
    {
        place = q.front()[0];
        dog = q.front()[1];
        int d = q.front()[2] ; 
        q.pop();
        if (place == B[1])
        {
            return d ;
        }

        visited[place][P[dog]] = 1;
        int plus = place + P[dog], minus = place - P[dog];
        push (plus , dog , d ) ; 
        push( minus , dog , d ) ; 
         
        for (int  v : here[place])
        {
            push ( place + P[v] , v , d ) ; 
            push ( place - P[v] , v , d ) ; 
        }
    }
    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(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