oj.uz

Submission #990015

# Submission time Handle Problem Language Result Execution time Memory
990015 2024-05-29T11:15:12 Z Mihailo Cyberland (APIO23_cyberland) C++17
97 / 100
 1000 ms 23508 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(50, 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 24 ms 4696 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 4696 KB Correct.
2 Correct 39 ms 4824 KB Correct.
3 Correct 37 ms 4700 KB Correct.
4 Correct 38 ms 4700 KB Correct.
5 Correct 38 ms 4700 KB Correct.
6 Correct 36 ms 6228 KB Correct.
7 Correct 48 ms 5976 KB Correct.
8 Correct 22 ms 7260 KB Correct.
9 Correct 35 ms 4444 KB Correct.
10 Correct 39 ms 4700 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 4896 KB Correct.
2 Correct 44 ms 4944 KB Correct.
3 Correct 41 ms 4948 KB Correct.
4 Correct 43 ms 4440 KB Correct.
5 Correct 42 ms 4656 KB Correct.
6 Correct 10 ms 6100 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 172 ms 12120 KB Correct.
2 Correct 186 ms 4696 KB Correct.
3 Correct 166 ms 4696 KB Correct.
4 Correct 172 ms 4700 KB Correct.
5 Correct 135 ms 4444 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 5076 KB Correct.
3 Correct 31 ms 5048 KB Correct.
4 Correct 41 ms 7352 KB Correct.
5 Correct 24 ms 4440 KB Correct.

Subtask #6
16.0 / 16.0

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

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 295 ms 4944 KB Correct.
2 Correct 49 ms 5204 KB Correct.
3 Correct 409 ms 16568 KB Correct.
4 Correct 307 ms 8016 KB Correct.
5 Correct 1000 ms 23508 KB Correct.
6 Correct 860 ms 22324 KB Correct.
7 Correct 316 ms 7940 KB Correct.
8 Correct 269 ms 5372 KB Correct.
9 Correct 224 ms 4944 KB Correct.
10 Correct 202 ms 5200 KB Correct.
11 Correct 257 ms 4944 KB Correct.
12 Correct 234 ms 4944 KB Correct.
13 Correct 260 ms 5096 KB Correct.
14 Correct 305 ms 11052 KB Correct.
15 Correct 296 ms 6480 KB Correct.
16 Correct 236 ms 5244 KB Correct.
17 Correct 265 ms 5200 KB Correct.
18 Correct 241 ms 4940 KB Correct.
19 Correct 498 ms 4948 KB Correct.
20 Correct 14 ms 4440 KB Correct.
21 Correct 15 ms 4696 KB Correct.
22 Correct 84 ms 6616 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 435 ms 5144 KB Correct.
2 Correct 83 ms 5204 KB Correct.
3 Incorrect 421 ms 15704 KB Wrong Answer.
4 Halted 0 ms 0 KB -