oj.uz

답안 #540657

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
540657 2022-03-21T10:46:01 Z FatihSolak Jakarta Skyscrapers (APIO15_skyscraper) C++17
0 / 100
 1000 ms 980 KB 
#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}));
        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}));
        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.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 980 KB Output is correct
2 Execution timed out 1097 ms 980 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 980 KB Output is correct
2 Execution timed out 1086 ms 980 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 980 KB Output is correct
2 Execution timed out 1088 ms 980 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 980 KB Output is correct
2 Execution timed out 1085 ms 980 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 980 KB Output is correct
2 Execution timed out 1086 ms 980 KB Time limit exceeded
3 Halted 0 ms 0 KB -