oj.uz

답안 #695272

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
695272 2023-02-04T21:02:09 Z 3omar_ahmed Jakarta Skyscrapers (APIO15_skyscraper) C++17
36 / 100
 1000 ms 1876 KB 
/**
 * author: 3omar_ahmed
 * date: 04-02-2023
 * Expert When :)
 */
#include <ext/rope>
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std ;
using namespace __gnu_cxx;
using namespace __gnu_pbds;
template<class x> using ordered_set = tree<x, null_type,less<x>, rb_tree_tag,tree_order_statistics_node_update>;
#define int long long
#define endl '\n'
#define all(a) a.begin() , a.end()
#define alr(a) a.rbegin() , a.rend()
const int N = 2e3 + 5;
int n, m;
vector < int > dis(N, INT_MAX);
vector < set < int > > possible(N);
int aa, bb;
int dij(int from, int to){
    priority_queue<pair < int ,int >> p;
    p.push({0 , from});
    dis[from] = 0;
    while(p.size()){
        auto node = p.top();
        p.pop();
        for(auto child : possible[node.second]){
            bool f1 = 0, f2 = 0;
            for(int i = 1, nod1 = i * child + node.second; ; i++, 
                                    nod1 = i * child + node.second){
                if(nod1 < n && dis[nod1] > node.first + i){
                    dis[nod1] = node.first + i ;
                    p.push({node.first + i, nod1});
                    if(possible[nod1].find(child) != 
                       possible[nod1].end())
                        break;
                } else if(nod1 >= n) break;
            }
            for(int i = 1, nod2 = -i * child + node.second; ; i++, 
                                    nod2 = -i * child + node.second){
                if(!f2 && nod2 >= 0 && dis[nod2] > node.first + i){
                    dis[nod2] = node.first + i ;
                    p.push({node.first + i, nod2});
                    if(possible[nod2].find(child) != 
                       possible[nod2].end())
                        break;
                } else if(nod2 < 0) break;
            }
        }
    }
    return dis[to];
}
signed main(){
    ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0);

    cin >> n >> m;
    int from = 0 , to = 1;
    for(int i = 0; i < m; i++){
        int b , p; cin >> b >> p;
        (i == 0? aa = b : (i == 1? bb = b : bb = bb));
        possible[b].insert(p);
    }
    int dist = dij(aa, bb);
    cout << (dist == INT_MAX? -1 : dist);
    return 0 ;
}

Compilation message

skyscraper.cpp: In function 'long long int dij(long long int, long long int)':
skyscraper.cpp:31:18: warning: unused variable 'f1' [-Wunused-variable]
   31 |             bool f1 = 0, f2 = 0;
      |                  ^~
skyscraper.cpp: In function 'int main()':
skyscraper.cpp:60:9: warning: unused variable 'from' [-Wunused-variable]
   60 |     int from = 0 , to = 1;
      |         ^~~~
skyscraper.cpp:60:20: warning: unused variable 'to' [-Wunused-variable]
   60 |     int from = 0 , to = 1;
      |                    ^~

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct

Subtask #2
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 2 ms 468 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 468 KB Output is correct
15 Correct 1 ms 468 KB Output is correct

Subtask #3
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 2 ms 468 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 468 KB Output is correct
15 Correct 2 ms 468 KB Output is correct
16 Correct 1 ms 468 KB Output is correct
17 Correct 30 ms 468 KB Output is correct
18 Correct 1 ms 468 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 3 ms 468 KB Output is correct
21 Correct 1 ms 468 KB Output is correct
22 Correct 1 ms 468 KB Output is correct
23 Correct 5 ms 512 KB Output is correct
24 Correct 37 ms 560 KB Output is correct
25 Correct 5 ms 468 KB Output is correct
26 Correct 1 ms 468 KB Output is correct
27 Correct 1 ms 468 KB Output is correct
28 Correct 1 ms 468 KB Output is correct
29 Correct 3 ms 596 KB Output is correct
30 Correct 1 ms 468 KB Output is correct
31 Correct 3 ms 468 KB Output is correct
32 Correct 2 ms 468 KB Output is correct
33 Correct 5 ms 852 KB Output is correct
34 Correct 5 ms 852 KB Output is correct

Subtask #4
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 468 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 2 ms 468 KB Output is correct
15 Correct 1 ms 468 KB Output is correct
16 Correct 1 ms 468 KB Output is correct
17 Correct 31 ms 468 KB Output is correct
18 Correct 1 ms 468 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 3 ms 468 KB Output is correct
21 Correct 1 ms 468 KB Output is correct
22 Correct 1 ms 468 KB Output is correct
23 Correct 5 ms 508 KB Output is correct
24 Correct 38 ms 552 KB Output is correct
25 Correct 6 ms 468 KB Output is correct
26 Correct 1 ms 468 KB Output is correct
27 Correct 1 ms 468 KB Output is correct
28 Correct 1 ms 468 KB Output is correct
29 Correct 2 ms 596 KB Output is correct
30 Correct 2 ms 512 KB Output is correct
31 Correct 2 ms 468 KB Output is correct
32 Correct 2 ms 468 KB Output is correct
33 Correct 5 ms 852 KB Output is correct
34 Correct 5 ms 852 KB Output is correct
35 Correct 496 ms 1620 KB Output is correct
36 Correct 62 ms 596 KB Output is correct
37 Execution timed out 1034 ms 1384 KB Time limit exceeded
38 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 2 ms 468 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 468 KB Output is correct
15 Correct 1 ms 468 KB Output is correct
16 Correct 0 ms 468 KB Output is correct
17 Correct 34 ms 468 KB Output is correct
18 Correct 1 ms 480 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 3 ms 468 KB Output is correct
21 Correct 1 ms 468 KB Output is correct
22 Correct 1 ms 468 KB Output is correct
23 Correct 5 ms 512 KB Output is correct
24 Correct 36 ms 552 KB Output is correct
25 Correct 4 ms 468 KB Output is correct
26 Correct 1 ms 468 KB Output is correct
27 Correct 1 ms 468 KB Output is correct
28 Correct 1 ms 468 KB Output is correct
29 Correct 3 ms 596 KB Output is correct
30 Correct 1 ms 468 KB Output is correct
31 Correct 2 ms 468 KB Output is correct
32 Correct 2 ms 468 KB Output is correct
33 Correct 6 ms 852 KB Output is correct
34 Correct 7 ms 852 KB Output is correct
35 Correct 492 ms 1672 KB Output is correct
36 Correct 49 ms 664 KB Output is correct
37 Correct 952 ms 1388 KB Output is correct
38 Execution timed out 1085 ms 1876 KB Time limit exceeded
39 Halted 0 ms 0 KB -