Submission #124234

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

int bfs()
{
    int place, dog;
    q.push({B[0],0,0}); 
    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];
        if (plus < n && !visited[plus][P[dog]])
            q.push({plus, dog , d + 1 }) ; 
        if (minus >= 0 && !visited[minus][P[dog]])
            q.push({minus, dog , d + 1 }) ; 
        for (int  v : here[place])
        {
            if( !visited[place][P[v]])
                q.push( {place , 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