oj.uz

Submission #695133

# Submission time Handle Problem Language Result Execution time Memory
695133 2023-02-04T18:32:17 Z Abito Jakarta Skyscrapers (APIO15_skyscraper) C++17
22 / 100
 108 ms 70388 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];
vector<int> d[N],p[N];
bool vis[N];
priority_queue<pair<int,int>> pq;
void getdiv(int x){
    for (int i=1;i*i<=x;i++){
        if (x%i) continue;
        int y=i,z=x/i;
        d[x].pb(y);
        if (y!=z) d[x].pb(z);
    }sort(d[x].begin(),d[x].end());
    return;
}
void dijkstra(){
    pq.push({0,a[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(){
    for (int i=1;i<N;i++){
        getdiv(i);
        dis[i]=INT_MAX;
    }cin>>n>>m;
    for (int i=0;i<m;i++){
        cin>>a[i]>>b[i];
        p[a[i]].pb(b[i]);
    }
    for (int i=0;i<n;i++) sort(p[i].begin(),p[i].end());
    for (int i=0;i<n;i++){
        for (int j=0;j<n;j++){
            if (i==j) continue;
            int dist=abs(i-j),x=0,y=0,ans=INT_MAX;
            while (x<d[dist].size() && y<p[i].size()){
                if (d[dist][x]==p[i][y]){
                    ans=dist/d[dist][x];
                    x++;
                    y++;
                    continue;
                }
                if (d[dist][x]<p[i][y]) x++;
                else y++;
            }
            if (ans==INT_MAX) continue;
            adj[i].pb({j,ans});
        }
    }dijkstra();
    if (dis[a[1]]==INT_MAX) cout<<-1<<endl;
    else cout<<dis[a[1]]<<endl;
    return 0;
}

Compilation message

skyscraper.cpp: In function 'int32_t main()':
skyscraper.cpp:50:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |             while (x<d[dist].size() && y<p[i].size()){
      |                    ~^~~~~~~~~~~~~~~
skyscraper.cpp:50:41: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |             while (x<d[dist].size() && y<p[i].size()){
      |                                        ~^~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 6100 KB Output is correct
2 Correct 29 ms 5996 KB Output is correct
3 Correct 29 ms 5992 KB Output is correct
4 Correct 34 ms 5968 KB Output is correct
5 Correct 31 ms 5976 KB Output is correct
6 Correct 30 ms 6100 KB Output is correct
7 Correct 31 ms 5964 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 6008 KB Output is correct
2 Correct 30 ms 5964 KB Output is correct
3 Correct 30 ms 6036 KB Output is correct
4 Correct 30 ms 5964 KB Output is correct
5 Correct 30 ms 6040 KB Output is correct
6 Correct 30 ms 6016 KB Output is correct
7 Correct 30 ms 6012 KB Output is correct
8 Correct 32 ms 5968 KB Output is correct
9 Correct 31 ms 6092 KB Output is correct
10 Correct 31 ms 6056 KB Output is correct
11 Correct 31 ms 6180 KB Output is correct
12 Correct 30 ms 6100 KB Output is correct
13 Correct 36 ms 6252 KB Output is correct
14 Correct 31 ms 6164 KB Output is correct
15 Correct 31 ms 6100 KB Output is correct

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 6096 KB Output is correct
2 Correct 30 ms 5964 KB Output is correct
3 Correct 31 ms 6020 KB Output is correct
4 Correct 30 ms 5984 KB Output is correct
5 Correct 30 ms 5964 KB Output is correct
6 Correct 31 ms 6028 KB Output is correct
7 Correct 30 ms 6100 KB Output is correct
8 Correct 33 ms 6100 KB Output is correct
9 Correct 29 ms 6060 KB Output is correct
10 Correct 30 ms 6140 KB Output is correct
11 Correct 31 ms 6172 KB Output is correct
12 Correct 31 ms 6092 KB Output is correct
13 Correct 32 ms 6348 KB Output is correct
14 Correct 31 ms 6080 KB Output is correct
15 Correct 31 ms 6128 KB Output is correct
16 Correct 32 ms 6148 KB Output is correct
17 Correct 43 ms 6512 KB Output is correct
18 Correct 59 ms 6244 KB Output is correct
19 Correct 62 ms 6152 KB Output is correct
20 Correct 108 ms 70312 KB Output is correct
21 Correct 36 ms 6092 KB Output is correct
22 Correct 67 ms 6160 KB Output is correct
23 Correct 63 ms 6160 KB Output is correct
24 Correct 76 ms 6432 KB Output is correct
25 Correct 79 ms 6360 KB Output is correct
26 Correct 47 ms 6368 KB Output is correct
27 Correct 46 ms 6220 KB Output is correct
28 Incorrect 101 ms 6532 KB Output isn't correct
29 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 6060 KB Output is correct
2 Correct 30 ms 6084 KB Output is correct
3 Correct 30 ms 6008 KB Output is correct
4 Correct 29 ms 6100 KB Output is correct
5 Correct 29 ms 6048 KB Output is correct
6 Correct 35 ms 5964 KB Output is correct
7 Correct 31 ms 5972 KB Output is correct
8 Correct 30 ms 6052 KB Output is correct
9 Correct 29 ms 6012 KB Output is correct
10 Correct 30 ms 6088 KB Output is correct
11 Correct 32 ms 6244 KB Output is correct
12 Correct 31 ms 6116 KB Output is correct
13 Correct 31 ms 6296 KB Output is correct
14 Correct 31 ms 6180 KB Output is correct
15 Correct 30 ms 6084 KB Output is correct
16 Correct 31 ms 6228 KB Output is correct
17 Correct 44 ms 6580 KB Output is correct
18 Correct 58 ms 6160 KB Output is correct
19 Correct 55 ms 6144 KB Output is correct
20 Correct 105 ms 70388 KB Output is correct
21 Correct 33 ms 6152 KB Output is correct
22 Correct 54 ms 6144 KB Output is correct
23 Correct 53 ms 6184 KB Output is correct
24 Correct 81 ms 6348 KB Output is correct
25 Correct 80 ms 6360 KB Output is correct
26 Correct 47 ms 6292 KB Output is correct
27 Correct 45 ms 6236 KB Output is correct
28 Incorrect 100 ms 6604 KB Output isn't correct
29 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 5992 KB Output is correct
2 Correct 30 ms 5988 KB Output is correct
3 Correct 30 ms 6068 KB Output is correct
4 Correct 30 ms 6092 KB Output is correct
5 Correct 29 ms 6084 KB Output is correct
6 Correct 32 ms 6048 KB Output is correct
7 Correct 33 ms 6100 KB Output is correct
8 Correct 31 ms 6008 KB Output is correct
9 Correct 29 ms 6036 KB Output is correct
10 Correct 30 ms 6112 KB Output is correct
11 Correct 33 ms 6200 KB Output is correct
12 Correct 30 ms 6100 KB Output is correct
13 Correct 31 ms 6340 KB Output is correct
14 Correct 32 ms 6164 KB Output is correct
15 Correct 32 ms 6192 KB Output is correct
16 Correct 31 ms 6168 KB Output is correct
17 Correct 44 ms 6572 KB Output is correct
18 Correct 60 ms 6248 KB Output is correct
19 Correct 55 ms 6100 KB Output is correct
20 Correct 107 ms 70364 KB Output is correct
21 Correct 32 ms 6108 KB Output is correct
22 Correct 54 ms 6160 KB Output is correct
23 Correct 57 ms 6240 KB Output is correct
24 Correct 79 ms 6448 KB Output is correct
25 Correct 79 ms 6392 KB Output is correct
26 Correct 48 ms 6296 KB Output is correct
27 Correct 45 ms 6252 KB Output is correct
28 Incorrect 102 ms 6564 KB Output isn't correct
29 Halted 0 ms 0 KB -