oj.uz

Submission #990017

# Submission time Handle Problem Language Result Execution time Memory
990017 2024-05-29T11:16:13 Z Mihailo Cyberland (APIO23_cyberland) C++17
97 / 100
 982 ms 22520 KB 
#include "cyberland.h"
#include <cassert>
#include <cstdio>
#include <bits/stdc++.h>
#define pll pair<long long, long long>
#define mp make_pair
#define pb push_back
#define xx first
#define yy second
using namespace std;
typedef long long ll;

vector<pair<__int128, long double> > adj[100100], v;
int a[100100], n, ks;
long double dis[100100], rez;

void dikstra() {
    priority_queue<pair<__int128, __int128> > q;
    pair<__int128, __int128> cur;
    for(int i=0; i<=n; i++) dis[i]=-1;
//    cout<<'\n';
    for(int j=0; j<v.size(); j++) {
        for(int i=0; i<adj[v[j].xx].size(); i++) {
            if(dis[adj[v[j].xx][i].xx]==-1) q.push(mp(v[j].yy-adj[v[j].xx][i].yy, adj[v[j].xx][i].xx));
        }
    }
    while(q.size()) {
        cur=q.top();
        q.pop();
//        cout<<cur.xx<<' '<<cur.yy<<'\n';
        if(dis[cur.yy]!=-1) continue;
        dis[cur.yy]=-cur.xx;
        for(int i=0; i<adj[cur.yy].size(); i++) {
            if(dis[adj[cur.yy][i].xx]==-1) q.push(mp(cur.xx-adj[cur.yy][i].yy, adj[cur.yy][i].xx));
        }
    }
}

double solve(int N, int M, int K, int H, std::vector<int> x, std::vector<int> y, std::vector<int> c, std::vector<int> arr) {
    K=min(70, K);
    for(int i=0; i<=N; i++) adj[i].clear();
    for(int i=0; i<M; i++) {
        adj[x[i]+1].pb(mp(y[i]+1, c[i]));
        adj[y[i]+1].pb(mp(x[i]+1, c[i]));
    }
    adj[H+1].clear();
    n=N;
    a[0]=1;
    a[1]=0;
    for(int i=1; i<arr.size(); i++) {
        a[i+1]=arr[i];
    }
    /////////
    adj[0].pb(mp(1, 0));
    v.clear();
    v.push_back(mp(0, 0));
    dikstra();
    if(dis[H+1]==-1) return -1;
    for(int i=1; i<=n; i++) {
        if(dis[i]==-1) a[i]=1;
    }
    adj[0].clear();
    /////////
    for(int i=1; i<=N; i++) {
        if(a[i]==0) adj[0].pb(mp(i, 0));
    }
    rez=1e30;
    ks=K;
    K++;
    while(K--) {
        dikstra();
        if(dis[H+1]>=0) rez=min(rez, dis[H+1]*(ll)pow(2, K));
        v.clear();
        for(int i=1; i<=N; i++) {
            if(a[i]==2) v.pb(mp(i, -dis[i]));
        }
        for(int i=0; i<=N; i++) {
            for(int j=0; j<adj[i].size(); j++) adj[i][j].yy*=2;
        }
    }
    return rez/((long double)pow(2, ks));
}

Compilation message

cyberland.cpp: In function 'void dikstra()':
cyberland.cpp:22:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<__int128, long double> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |     for(int j=0; j<v.size(); j++) {
      |                  ~^~~~~~~~~
cyberland.cpp:23:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<__int128, long double> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |         for(int i=0; i<adj[v[j].xx].size(); i++) {
      |                      ~^~~~~~~~~~~~~~~~~~~~
cyberland.cpp:33:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<__int128, long double> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |         for(int i=0; i<adj[cur.yy].size(); i++) {
      |                      ~^~~~~~~~~~~~~~~~~~~
cyberland.cpp: In function 'double solve(int, int, int, int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
cyberland.cpp:50:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |     for(int i=1; i<arr.size(); i++) {
      |                  ~^~~~~~~~~~~
cyberland.cpp:78:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<__int128, long double> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |             for(int j=0; j<adj[i].size(); j++) adj[i][j].yy*=2;
      |                          ~^~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 4700 KB Correct.
2 Correct 25 ms 4700 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 4696 KB Correct.
2 Correct 65 ms 4876 KB Correct.
3 Correct 38 ms 4700 KB Correct.
4 Correct 38 ms 4700 KB Correct.
5 Correct 38 ms 4700 KB Correct.
6 Correct 36 ms 6236 KB Correct.
7 Correct 49 ms 6084 KB Correct.
8 Correct 21 ms 7260 KB Correct.
9 Correct 35 ms 4672 KB Correct.
10 Correct 60 ms 4440 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 4696 KB Correct.
2 Correct 74 ms 4696 KB Correct.
3 Correct 41 ms 4952 KB Correct.
4 Correct 42 ms 4664 KB Correct.
5 Correct 45 ms 4668 KB Correct.
6 Correct 15 ms 6104 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 172 ms 12472 KB Correct.
2 Correct 204 ms 4744 KB Correct.
3 Correct 170 ms 5060 KB Correct.
4 Correct 200 ms 4752 KB Correct.
5 Correct 130 ms 4444 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 4980 KB Correct.
2 Correct 31 ms 4956 KB Correct.
3 Correct 31 ms 5008 KB Correct.
4 Correct 38 ms 7416 KB Correct.
5 Correct 28 ms 4440 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 5124 KB Correct.
2 Correct 34 ms 4956 KB Correct.
3 Correct 33 ms 14172 KB Correct.
4 Correct 26 ms 6704 KB Correct.
5 Correct 33 ms 4700 KB Correct.
6 Correct 53 ms 5044 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 266 ms 4948 KB Correct.
2 Correct 50 ms 5204 KB Correct.
3 Correct 412 ms 16712 KB Correct.
4 Correct 308 ms 8016 KB Correct.
5 Correct 982 ms 22520 KB Correct.
6 Correct 859 ms 21660 KB Correct.
7 Correct 311 ms 7760 KB Correct.
8 Correct 263 ms 5384 KB Correct.
9 Correct 254 ms 5060 KB Correct.
10 Correct 200 ms 4996 KB Correct.
11 Correct 255 ms 5004 KB Correct.
12 Correct 255 ms 5176 KB Correct.
13 Correct 274 ms 5196 KB Correct.
14 Correct 311 ms 11028 KB Correct.
15 Correct 318 ms 6484 KB Correct.
16 Correct 236 ms 5092 KB Correct.
17 Correct 268 ms 5164 KB Correct.
18 Correct 242 ms 4940 KB Correct.
19 Correct 497 ms 5200 KB Correct.
20 Correct 14 ms 4660 KB Correct.
21 Correct 15 ms 4792 KB Correct.
22 Correct 83 ms 6652 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Incorrect 612 ms 5204 KB Double -1.56915e+09 violates the range [-1, 1e+18]
2 Halted 0 ms 0 KB -