oj.uz

Submission #990012

# Submission time Handle Problem Language Result Execution time Memory
990012 2024-05-29T11:11:12 Z Mihailo Cyberland (APIO23_cyberland) C++17
97 / 100
 799 ms 23156 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, __int128> > adj[100100], v;
int a[100100], n, ks;
__int128 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, __int128> >::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, __int128> >::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, __int128> >::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, __int128> >::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 17 ms 4700 KB Correct.
2 Correct 17 ms 4700 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 4812 KB Correct.
2 Correct 26 ms 4832 KB Correct.
3 Correct 26 ms 4696 KB Correct.
4 Correct 25 ms 4700 KB Correct.
5 Correct 25 ms 4872 KB Correct.
6 Correct 28 ms 6216 KB Correct.
7 Correct 34 ms 6160 KB Correct.
8 Correct 16 ms 7260 KB Correct.
9 Correct 22 ms 4680 KB Correct.
10 Correct 21 ms 4444 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 4912 KB Correct.
2 Correct 32 ms 5116 KB Correct.
3 Correct 27 ms 4956 KB Correct.
4 Correct 26 ms 4440 KB Correct.
5 Correct 26 ms 4444 KB Correct.
6 Correct 7 ms 6100 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 132 ms 12132 KB Correct.
2 Correct 129 ms 4812 KB Correct.
3 Correct 96 ms 4812 KB Correct.
4 Correct 103 ms 4784 KB Correct.
5 Correct 62 ms 4440 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 4952 KB Correct.
2 Correct 22 ms 5092 KB Correct.
3 Correct 22 ms 4956 KB Correct.
4 Correct 30 ms 7416 KB Correct.
5 Correct 17 ms 4664 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 4956 KB Correct.
2 Correct 22 ms 4956 KB Correct.
3 Correct 33 ms 14160 KB Correct.
4 Correct 19 ms 6836 KB Correct.
5 Correct 21 ms 4680 KB Correct.
6 Correct 24 ms 4952 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 169 ms 4936 KB Correct.
2 Correct 34 ms 5208 KB Correct.
3 Correct 292 ms 16456 KB Correct.
4 Correct 221 ms 8016 KB Correct.
5 Correct 799 ms 23156 KB Correct.
6 Correct 686 ms 21744 KB Correct.
7 Correct 219 ms 7760 KB Correct.
8 Correct 162 ms 5456 KB Correct.
9 Correct 148 ms 4988 KB Correct.
10 Correct 129 ms 5060 KB Correct.
11 Correct 149 ms 4944 KB Correct.
12 Correct 153 ms 4952 KB Correct.
13 Correct 172 ms 5064 KB Correct.
14 Correct 221 ms 11044 KB Correct.
15 Correct 199 ms 6568 KB Correct.
16 Correct 152 ms 5008 KB Correct.
17 Correct 172 ms 4952 KB Correct.
18 Correct 161 ms 4956 KB Correct.
19 Correct 332 ms 4948 KB Correct.
20 Correct 7 ms 4444 KB Correct.
21 Correct 11 ms 4696 KB Correct.
22 Correct 62 ms 6668 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Incorrect 434 ms 5096 KB Double -1.23861e+08 violates the range [-1, 1e+18]
2 Halted 0 ms 0 KB -