Submission #1308739

#	Time	Username	Problem	Language	Result	Execution time	Memory
1308739		eshanahmed	Jakarta Skyscrapers (APIO15_skyscraper)	C++20	0 / 100	1 ms	652 KiB

skyscraper

// ﷽
#include <bits/stdc++.h>
using namespace std;
#define ll long long

#define cinv(c) for(auto &i : c) cin >> i;

void solve() {
    ll n,m; 
    cin>>n>>m;
    vector<ll> con[n];
    for(auto i=0;i<m;i++){
        ll a,b;
        cin>>a>>b;
        for(auto i=(a%b);i<n;i+=b){
            con[a].push_back(i);
        }   
    }
    ll t=-1,g=1;
    vector<ll> seen(n,0);
    set<ll> tempbfs,bfs;
    seen[0]=1;
    bfs.insert(0);
    while(bfs.size()>0){
        for(auto i:bfs){
            g++;
            for(auto y:con[i]){
                if(y==1){
                    t=g+1;
                    goto end;
                }
                if(seen[y])continue;
                seen[y]=1;
                tempbfs.insert(y);
            }
            g--;
        }
        bfs.clear();
        bfs=tempbfs;
        tempbfs.clear();
        g+=2;
    }
    end:
    cout<<t<<endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    ll t=1;
    while (t--) solve();
}

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