Submission #540664

#	Time	Username	Problem	Language	Result	Execution time	Memory
540664		FatihSolak	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	0 / 100	3 ms	980 KiB

skyscraper

#include <bits/stdc++.h>
#define N 30005
using namespace std;
vector<int> v[N];
bool vis[N];
map<pair<int,int>,set<pair<int,int>>> mp;
set<pair<int,int>> extend;
int n;
void add(pair<int,int> a,pair<int,int> b){
    //cout << a.first << " " << a.second << " " << b.first << " " << b.second << endl;
    if(mp[a].size() && mp[a].lower_bound({b.second+a.first + 1,0}) != mp[a].begin()){
        auto c = *prev(mp[a].lower_bound({b.second+a.first + 1,0}));
        if(c.second >= a.first - 1){
            b.first = min(b.first,c.first);
            b.second = max(b.second,c.second);
            mp[a].erase(c);
        }
    }
    if(mp[a].size() && mp[a].lower_bound({b.first,0}) != mp[a].begin()){
        auto c = *prev(mp[a].lower_bound({b.first,0}));
        if(c.second >= a.first - 1){
            b.first = min(b.first,c.first);
            b.second = max(b.second,c.second);
            mp[a].erase(c);
        }
    }
    //cout << b.first << " " << b.second << endl;
    mp[a].insert(b);
    if(extend.find(a) != extend.end())
        extend.erase(a);
    if(mp[a].size() > 1)
        extend.insert(a);
    int l = mp[a].begin()->first;
    int r = mp[a].rbegin()->second;
    if(l - a.first >= 0 || r + a.first < n)
        extend.insert(a);
}
void solve(){
    int m;
    cin >> n >> m;
    int st = -1;
    for(int i=1;i<=m;i++){
        int a,b;
        cin >> a >> b;
        if(st == -1)st = a;
        v[a].push_back(b);
    }
    vector<int> nws;
    vis[st] = 1;
    nws.push_back(st);
    int cnt = 0;
    while(nws.size() || extend.size()){
        vector<int> nxt;
        for(auto u:nws){
            if(u == 1){
                cout <<  cnt << endl;
                return;
            }
            //cout << u << endl;
            for(auto c:v[u]){
                add({c,u % c},{u,u});
            }
        }
        vector<pair<int,int>> tmp;
        for(auto u:extend){
            //cout << u.first << " " << u.second << endl;
            tmp.push_back(u);
        }
        for(auto u:tmp){
            vector<pair<int,int>> tmp2;
            for(auto c:mp[u]){
                if(c.first - u.first >= 0)
                    tmp2.push_back({c.first - u.first,c.first - u.first});
                if(c.second + u.first < n)
                    tmp2.push_back({c.second + u.first,c.second + u.first});
            }
            for(auto c:tmp2){
                if(!vis[c.first]){
                    vis[c.first] = 1;
                    nxt.push_back(c.first);
                }
                add(u,c);
            }
        }
        swap(nws,nxt);  
        cnt++;
    }
    cout << -1 << endl;
}

int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    #ifdef Local
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
    #endif
    int t=1;
    //cin>>t;
    while(t--){
        solve();
    }
    #ifdef Local
    cout<<endl<<fixed<<setprecision(2)<<1000.0 * clock() / CLOCKS_PER_SEC<< " milliseconds ";
    #endif
}

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