oj.uz

Submission #695114

# Submission time Handle Problem Language Result Execution time Memory
695114 2023-02-04T18:04:49 Z Abito Jakarta Skyscrapers (APIO15_skyscraper) C++17
36 / 100
 1000 ms 65480 KB 
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define F first
#define S second
#define int long long
const int N=3e4+5;
int a[N],b[N],n,m,dis[N];
vector<pair<int,int>> adj[N];
priority_queue<pair<int,int>> pq;
bool vis[N];
void dijkstra(){
    pq.push({0,0});
    while (!pq.empty()){
        pair<int,int> x=pq.top();
        x.F*=-1;
        pq.pop();
        if (vis[x.S]) continue;
        vis[x.S]=true;
        for (auto u:adj[x.S]){
            if (dis[u.F]<=x.F+u.S) continue;
            dis[u.F]=x.F+u.S;
            pq.push({-dis[u.F],u.F});
        }
    }return;
}
int32_t main(){
    cin>>n>>m;
    for (int i=1;i<N;i++) dis[i]=INT_MAX;
    for (int i=0;i<m;i++) cin>>a[i]>>b[i];
    for (int i=0;i<m;i++){
        for (int j=0;j<m;j++){
            if (i==j) continue;
            if (abs(a[i]-a[j])%b[i]) continue;
            adj[i].pb({j,abs(a[i]-a[j])/b[i]});
            //cout<<i<<' '<<j<<' '<<abs(a[i]-a[j])/b[i]<<endl;
        }
    }
    dijkstra();
    if (dis[1]==INT_MAX) cout<<-1<<endl;
    else cout<<dis[1]<<endl;
    return 0;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1236 KB Output is correct
2 Correct 1 ms 1236 KB Output is correct
3 Correct 1 ms 1236 KB Output is correct
4 Correct 1 ms 1236 KB Output is correct
5 Correct 1 ms 1236 KB Output is correct
6 Correct 1 ms 1236 KB Output is correct
7 Correct 1 ms 1236 KB Output is correct
8 Correct 1 ms 1236 KB Output is correct
9 Correct 1 ms 1236 KB Output is correct
10 Correct 2 ms 1364 KB Output is correct
11 Correct 25 ms 5472 KB Output is correct
12 Correct 71 ms 65076 KB Output is correct
13 Correct 74 ms 65480 KB Output is correct
14 Correct 24 ms 4104 KB Output is correct
15 Correct 23 ms 4116 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1236 KB Output is correct
2 Correct 1 ms 1236 KB Output is correct
3 Correct 1 ms 1236 KB Output is correct
4 Correct 1 ms 1236 KB Output is correct
5 Correct 1 ms 1236 KB Output is correct
6 Correct 1 ms 1236 KB Output is correct
7 Correct 1 ms 1236 KB Output is correct
8 Correct 1 ms 1236 KB Output is correct
9 Correct 1 ms 1236 KB Output is correct
10 Correct 2 ms 1364 KB Output is correct
11 Correct 25 ms 5460 KB Output is correct
12 Correct 71 ms 65036 KB Output is correct
13 Correct 70 ms 65464 KB Output is correct
14 Correct 23 ms 4212 KB Output is correct
15 Correct 23 ms 4220 KB Output is correct
16 Correct 5 ms 1748 KB Output is correct
17 Correct 18 ms 2460 KB Output is correct
18 Correct 6 ms 1236 KB Output is correct
19 Correct 3 ms 1280 KB Output is correct
20 Correct 74 ms 65452 KB Output is correct
21 Correct 9 ms 1364 KB Output is correct
22 Correct 4 ms 1236 KB Output is correct
23 Correct 6 ms 1364 KB Output is correct
24 Correct 20 ms 1592 KB Output is correct
25 Correct 22 ms 1572 KB Output is correct
26 Correct 68 ms 59484 KB Output is correct
27 Correct 71 ms 61216 KB Output is correct
28 Correct 23 ms 1684 KB Output is correct
29 Correct 4 ms 1748 KB Output is correct
30 Correct 1 ms 1236 KB Output is correct
31 Correct 3 ms 1492 KB Output is correct
32 Correct 3 ms 1364 KB Output is correct
33 Correct 27 ms 4200 KB Output is correct
34 Correct 27 ms 4228 KB Output is correct

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1236 KB Output is correct
2 Correct 1 ms 1236 KB Output is correct
3 Correct 1 ms 1236 KB Output is correct
4 Correct 1 ms 1236 KB Output is correct
5 Correct 1 ms 1236 KB Output is correct
6 Correct 1 ms 1236 KB Output is correct
7 Correct 1 ms 1236 KB Output is correct
8 Correct 1 ms 1236 KB Output is correct
9 Correct 1 ms 1236 KB Output is correct
10 Correct 2 ms 1364 KB Output is correct
11 Correct 26 ms 5500 KB Output is correct
12 Correct 77 ms 65004 KB Output is correct
13 Correct 72 ms 65372 KB Output is correct
14 Correct 24 ms 4180 KB Output is correct
15 Correct 25 ms 4180 KB Output is correct
16 Correct 6 ms 1720 KB Output is correct
17 Correct 20 ms 2532 KB Output is correct
18 Correct 6 ms 1236 KB Output is correct
19 Correct 3 ms 1400 KB Output is correct
20 Correct 74 ms 65404 KB Output is correct
21 Correct 9 ms 1412 KB Output is correct
22 Correct 4 ms 1236 KB Output is correct
23 Correct 7 ms 1284 KB Output is correct
24 Correct 20 ms 1640 KB Output is correct
25 Correct 21 ms 1480 KB Output is correct
26 Correct 67 ms 59416 KB Output is correct
27 Correct 68 ms 61132 KB Output is correct
28 Correct 24 ms 1708 KB Output is correct
29 Correct 6 ms 1788 KB Output is correct
30 Correct 1 ms 1236 KB Output is correct
31 Correct 4 ms 1404 KB Output is correct
32 Correct 3 ms 1400 KB Output is correct
33 Correct 25 ms 4180 KB Output is correct
34 Correct 26 ms 4148 KB Output is correct
35 Execution timed out 1080 ms 21584 KB Time limit exceeded
36 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1236 KB Output is correct
2 Correct 1 ms 1236 KB Output is correct
3 Correct 1 ms 1236 KB Output is correct
4 Correct 1 ms 1236 KB Output is correct
5 Correct 1 ms 1236 KB Output is correct
6 Correct 1 ms 1236 KB Output is correct
7 Correct 1 ms 1236 KB Output is correct
8 Correct 1 ms 1236 KB Output is correct
9 Correct 1 ms 1236 KB Output is correct
10 Correct 2 ms 1364 KB Output is correct
11 Correct 26 ms 5460 KB Output is correct
12 Correct 72 ms 65100 KB Output is correct
13 Correct 75 ms 65416 KB Output is correct
14 Correct 24 ms 4180 KB Output is correct
15 Correct 24 ms 4144 KB Output is correct
16 Correct 5 ms 1748 KB Output is correct
17 Correct 21 ms 2516 KB Output is correct
18 Correct 6 ms 1316 KB Output is correct
19 Correct 2 ms 1236 KB Output is correct
20 Correct 72 ms 65416 KB Output is correct
21 Correct 8 ms 1364 KB Output is correct
22 Correct 4 ms 1272 KB Output is correct
23 Correct 6 ms 1364 KB Output is correct
24 Correct 21 ms 1596 KB Output is correct
25 Correct 21 ms 1556 KB Output is correct
26 Correct 70 ms 59500 KB Output is correct
27 Correct 72 ms 61236 KB Output is correct
28 Correct 21 ms 1740 KB Output is correct
29 Correct 5 ms 1748 KB Output is correct
30 Correct 1 ms 1272 KB Output is correct
31 Correct 3 ms 1492 KB Output is correct
32 Correct 3 ms 1400 KB Output is correct
33 Correct 24 ms 4136 KB Output is correct
34 Correct 24 ms 4164 KB Output is correct
35 Execution timed out 1082 ms 22796 KB Time limit exceeded
36 Halted 0 ms 0 KB -