oj.uz

Submission #540672

# Submission time Handle Problem Language Result Execution time Memory
540672 2022-03-21T11:00:10 Z FatihSolak Jakarta Skyscrapers (APIO15_skyscraper) C++17
22 / 100
 1000 ms 1528 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}));
        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;
    int nd = -1;
    for(int i=1;i<=m;i++){
        int a,b;
        cin >> a >> b;
        if(st == -1)st = a;
        else if(nd == -1)nd = 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 == nd){
                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
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 980 KB Output is correct
2 Correct 1 ms 980 KB Output is correct
3 Correct 1 ms 980 KB Output is correct
4 Correct 1 ms 980 KB Output is correct
5 Correct 1 ms 980 KB Output is correct
6 Correct 1 ms 1032 KB Output is correct
7 Correct 1 ms 1036 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 980 KB Output is correct
2 Correct 1 ms 980 KB Output is correct
3 Correct 1 ms 980 KB Output is correct
4 Correct 1 ms 980 KB Output is correct
5 Correct 1 ms 980 KB Output is correct
6 Correct 1 ms 980 KB Output is correct
7 Correct 1 ms 980 KB Output is correct
8 Correct 1 ms 980 KB Output is correct
9 Correct 1 ms 980 KB Output is correct
10 Correct 1 ms 1036 KB Output is correct
11 Correct 1 ms 1044 KB Output is correct
12 Correct 1 ms 980 KB Output is correct
13 Correct 1 ms 980 KB Output is correct
14 Correct 135 ms 1464 KB Output is correct
15 Correct 5 ms 1496 KB Output is correct

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 980 KB Output is correct
2 Correct 1 ms 980 KB Output is correct
3 Correct 1 ms 980 KB Output is correct
4 Correct 1 ms 1028 KB Output is correct
5 Correct 1 ms 980 KB Output is correct
6 Correct 1 ms 980 KB Output is correct
7 Correct 1 ms 980 KB Output is correct
8 Correct 1 ms 980 KB Output is correct
9 Correct 1 ms 1028 KB Output is correct
10 Correct 1 ms 980 KB Output is correct
11 Correct 1 ms 980 KB Output is correct
12 Correct 1 ms 980 KB Output is correct
13 Correct 1 ms 980 KB Output is correct
14 Correct 136 ms 1492 KB Output is correct
15 Correct 5 ms 1492 KB Output is correct
16 Correct 1 ms 980 KB Output is correct
17 Correct 5 ms 1304 KB Output is correct
18 Execution timed out 1080 ms 980 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 980 KB Output is correct
2 Correct 1 ms 980 KB Output is correct
3 Correct 1 ms 1036 KB Output is correct
4 Correct 1 ms 980 KB Output is correct
5 Correct 1 ms 980 KB Output is correct
6 Correct 1 ms 980 KB Output is correct
7 Correct 1 ms 980 KB Output is correct
8 Correct 1 ms 980 KB Output is correct
9 Correct 1 ms 980 KB Output is correct
10 Correct 1 ms 1036 KB Output is correct
11 Correct 1 ms 980 KB Output is correct
12 Correct 1 ms 1040 KB Output is correct
13 Correct 2 ms 980 KB Output is correct
14 Correct 140 ms 1520 KB Output is correct
15 Correct 5 ms 1492 KB Output is correct
16 Correct 1 ms 980 KB Output is correct
17 Correct 5 ms 1236 KB Output is correct
18 Execution timed out 1092 ms 980 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 980 KB Output is correct
2 Correct 1 ms 980 KB Output is correct
3 Correct 1 ms 980 KB Output is correct
4 Correct 1 ms 1032 KB Output is correct
5 Correct 1 ms 980 KB Output is correct
6 Correct 1 ms 980 KB Output is correct
7 Correct 1 ms 1032 KB Output is correct
8 Correct 1 ms 980 KB Output is correct
9 Correct 1 ms 1032 KB Output is correct
10 Correct 1 ms 980 KB Output is correct
11 Correct 1 ms 980 KB Output is correct
12 Correct 1 ms 1048 KB Output is correct
13 Correct 2 ms 1048 KB Output is correct
14 Correct 134 ms 1528 KB Output is correct
15 Correct 5 ms 1492 KB Output is correct
16 Correct 1 ms 980 KB Output is correct
17 Correct 5 ms 1236 KB Output is correct
18 Execution timed out 1089 ms 980 KB Time limit exceeded
19 Halted 0 ms 0 KB -