oj.uz

Submission #990013

# Submission time Handle Problem Language Result Execution time Memory
990013 2024-05-29T11:13:09 Z Mihailo Cyberland (APIO23_cyberland) C++17
97 / 100
 981 ms 22416 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(100, 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 4952 KB Correct.
2 Correct 24 ms 4700 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 4700 KB Correct.
2 Correct 38 ms 4808 KB Correct.
3 Correct 37 ms 4700 KB Correct.
4 Correct 38 ms 4756 KB Correct.
5 Correct 39 ms 4700 KB Correct.
6 Correct 36 ms 6232 KB Correct.
7 Correct 47 ms 6136 KB Correct.
8 Correct 24 ms 7256 KB Correct.
9 Correct 35 ms 4444 KB Correct.
10 Correct 37 ms 4664 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 4696 KB Correct.
2 Correct 44 ms 4948 KB Correct.
3 Correct 41 ms 4956 KB Correct.
4 Correct 42 ms 4656 KB Correct.
5 Correct 42 ms 4444 KB Correct.
6 Correct 10 ms 6104 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 170 ms 12264 KB Correct.
2 Correct 185 ms 4824 KB Correct.
3 Correct 158 ms 4696 KB Correct.
4 Correct 181 ms 4700 KB Correct.
5 Correct 134 ms 4440 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 4952 KB Correct.
2 Correct 31 ms 4956 KB Correct.
3 Correct 31 ms 5080 KB Correct.
4 Correct 39 ms 7324 KB Correct.
5 Correct 25 ms 4440 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 4952 KB Correct.
2 Correct 30 ms 4952 KB Correct.
3 Correct 30 ms 14164 KB Correct.
4 Correct 25 ms 6736 KB Correct.
5 Correct 31 ms 4696 KB Correct.
6 Correct 35 ms 4956 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 269 ms 4948 KB Correct.
2 Correct 50 ms 5204 KB Correct.
3 Correct 412 ms 16440 KB Correct.
4 Correct 313 ms 8016 KB Correct.
5 Correct 981 ms 22416 KB Correct.
6 Correct 862 ms 21944 KB Correct.
7 Correct 323 ms 8128 KB Correct.
8 Correct 263 ms 5204 KB Correct.
9 Correct 221 ms 4948 KB Correct.
10 Correct 200 ms 5204 KB Correct.
11 Correct 253 ms 4944 KB Correct.
12 Correct 242 ms 4948 KB Correct.
13 Correct 252 ms 4960 KB Correct.
14 Correct 303 ms 11036 KB Correct.
15 Correct 301 ms 6648 KB Correct.
16 Correct 230 ms 5192 KB Correct.
17 Correct 266 ms 4976 KB Correct.
18 Correct 244 ms 4956 KB Correct.
19 Correct 466 ms 4912 KB Correct.
20 Correct 14 ms 4444 KB Correct.
21 Correct 15 ms 4840 KB Correct.
22 Correct 84 ms 6628 KB Correct.

Subtask #8
0.0 / 3.0

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