oj.uz

Submission #990014

# Submission time Handle Problem Language Result Execution time Memory
990014 2024-05-29T11:14:07 Z Mihailo Cyberland (APIO23_cyberland) C++17
97 / 100
 957 ms 22848 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(30, 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 4696 KB Correct.
2 Correct 29 ms 4700 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 4856 KB Correct.
2 Correct 39 ms 4696 KB Correct.
3 Correct 37 ms 4848 KB Correct.
4 Correct 38 ms 4700 KB Correct.
5 Correct 38 ms 4848 KB Correct.
6 Correct 44 ms 6212 KB Correct.
7 Correct 46 ms 5980 KB Correct.
8 Correct 21 ms 7256 KB Correct.
9 Correct 35 ms 4656 KB Correct.
10 Correct 35 ms 4444 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 4796 KB Correct.
2 Correct 45 ms 4700 KB Correct.
3 Correct 41 ms 4952 KB Correct.
4 Correct 48 ms 4672 KB Correct.
5 Correct 46 ms 4440 KB Correct.
6 Correct 10 ms 6104 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 169 ms 12120 KB Correct.
2 Correct 182 ms 4700 KB Correct.
3 Correct 162 ms 4760 KB Correct.
4 Correct 172 ms 4696 KB Correct.
5 Correct 141 ms 4440 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 4952 KB Correct.
2 Correct 31 ms 4952 KB Correct.
3 Correct 31 ms 5084 KB Correct.
4 Correct 39 ms 7460 KB Correct.
5 Correct 24 ms 4696 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 5100 KB Correct.
2 Correct 29 ms 4952 KB Correct.
3 Correct 33 ms 14172 KB Correct.
4 Correct 27 ms 6768 KB Correct.
5 Correct 31 ms 4444 KB Correct.
6 Correct 36 ms 4956 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 262 ms 4936 KB Correct.
2 Correct 51 ms 5212 KB Correct.
3 Correct 407 ms 16464 KB Correct.
4 Correct 312 ms 8020 KB Correct.
5 Correct 957 ms 22848 KB Correct.
6 Correct 852 ms 21732 KB Correct.
7 Correct 317 ms 7764 KB Correct.
8 Correct 263 ms 5200 KB Correct.
9 Correct 230 ms 5204 KB Correct.
10 Correct 199 ms 5200 KB Correct.
11 Correct 254 ms 4968 KB Correct.
12 Correct 237 ms 4948 KB Correct.
13 Correct 249 ms 5200 KB Correct.
14 Correct 307 ms 11040 KB Correct.
15 Correct 295 ms 6480 KB Correct.
16 Correct 239 ms 5052 KB Correct.
17 Correct 273 ms 4956 KB Correct.
18 Correct 242 ms 4956 KB Correct.
19 Correct 499 ms 4948 KB Correct.
20 Correct 14 ms 4444 KB Correct.
21 Correct 15 ms 4784 KB Correct.
22 Correct 83 ms 6696 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 256 ms 4948 KB Correct.
2 Correct 50 ms 5208 KB Correct.
3 Incorrect 271 ms 18000 KB Wrong Answer.
4 Halted 0 ms 0 KB -