oj.uz

Submission #990007

# Submission time Handle Problem Language Result Execution time Memory
990007 2024-05-29T11:04:16 Z Mihailo Cyberland (APIO23_cyberland) C++17
97 / 100
 3000 ms 24120 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) {
    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:49:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |     for(int i=1; i<arr.size(); i++) {
      |                  ~^~~~~~~~~~~
cyberland.cpp:77: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]
   77 |             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 18 ms 4700 KB Correct.
2 Correct 28 ms 4956 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 4700 KB Correct.
2 Correct 25 ms 4700 KB Correct.
3 Correct 24 ms 4864 KB Correct.
4 Correct 25 ms 4700 KB Correct.
5 Correct 24 ms 4696 KB Correct.
6 Correct 26 ms 5988 KB Correct.
7 Correct 34 ms 6156 KB Correct.
8 Correct 16 ms 7256 KB Correct.
9 Correct 23 ms 4672 KB Correct.
10 Correct 22 ms 4444 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 4700 KB Correct.
2 Correct 29 ms 4896 KB Correct.
3 Correct 31 ms 4956 KB Correct.
4 Correct 27 ms 4444 KB Correct.
5 Correct 28 ms 4440 KB Correct.
6 Correct 8 ms 6104 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 131 ms 12260 KB Correct.
2 Correct 116 ms 5812 KB Correct.
3 Correct 124 ms 5712 KB Correct.
4 Correct 106 ms 5796 KB Correct.
5 Correct 63 ms 5408 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 4956 KB Correct.
2 Correct 23 ms 5016 KB Correct.
3 Correct 22 ms 5208 KB Correct.
4 Correct 36 ms 7364 KB Correct.
5 Correct 17 ms 4684 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 4956 KB Correct.
2 Correct 32 ms 5136 KB Correct.
3 Correct 56 ms 14016 KB Correct.
4 Correct 20 ms 6696 KB Correct.
5 Correct 39 ms 4444 KB Correct.
6 Correct 24 ms 4956 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 173 ms 5068 KB Correct.
2 Correct 36 ms 5344 KB Correct.
3 Correct 319 ms 18816 KB Correct.
4 Correct 245 ms 10580 KB Correct.
5 Correct 860 ms 24120 KB Correct.
6 Correct 739 ms 23712 KB Correct.
7 Correct 233 ms 10000 KB Correct.
8 Correct 169 ms 7288 KB Correct.
9 Correct 151 ms 5972 KB Correct.
10 Correct 137 ms 6140 KB Correct.
11 Correct 163 ms 6864 KB Correct.
12 Correct 155 ms 5964 KB Correct.
13 Correct 150 ms 5968 KB Correct.
14 Correct 210 ms 13140 KB Correct.
15 Correct 186 ms 8528 KB Correct.
16 Correct 133 ms 5992 KB Correct.
17 Correct 172 ms 6032 KB Correct.
18 Correct 168 ms 6004 KB Correct.
19 Correct 363 ms 7024 KB Correct.
20 Correct 8 ms 4700 KB Correct.
21 Correct 10 ms 4860 KB Correct.
22 Correct 63 ms 6784 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3063 ms 4700 KB Time limit exceeded
2 Halted 0 ms 0 KB -