oj.uz

Submission #879138

# Submission time Handle Problem Language Result Execution time Memory
879138 2023-11-26T12:39:07 Z leanchec Cyberland (APIO23_cyberland) C++17
97 / 100
 2016 ms 79884 KB 
#include "cyberland.h"
#include<bits/stdc++.h>
using namespace std;

vector<pair<int,int>> adj[100100];
bool visited[100100]={};

void dfs(int cur, int H){
    visited[cur]=true;
    for(int i=0; i<(int)adj[cur].size(); i++){
        int viz=adj[cur][i].first;
        if(visited[viz] || viz==H)continue;
        dfs(viz, H);
    }
}

double solve(int N, int M, int K, int H, vector<int> x, vector<int>
y, vector<int> c, vector<int> arr){
    K=min(K, 50);
    for(int i=0; i<N; i++){
        adj[i].clear();
        visited[i]=0;
    }
    for(int i=0; i<M; i++){
        adj[x[i]].push_back({y[i], c[i]});
        adj[y[i]].push_back({x[i], c[i]});
    }

    double dist[100100][75], po[74];
    bool achou[100100][75];

    po[0]=1;
    for(int i=1; i<=69; i++)po[i]=po[i-1]*2;

    for(int i=0; i<N; i++){
        for(int j=0; j<=K; j++){
            dist[i][j]=1e15;
            achou[i][j]=0;
        }
    }

    set<array<double, 3>> ss;

    ss.insert({0, H, 0});
    dist[H][0]=0;

    while(!ss.empty()){
        array<double, 3> curtop=*ss.begin();
        ss.erase(ss.begin());

        int cur=curtop[1];
        int curk=curtop[2];

        if(achou[cur][curk])continue;
        achou[cur][curk]=true;

        for(int i=0; i<(int)adj[cur].size(); i++){
            int viz=adj[cur][i].first;
            if(viz==H)continue;
            double w=adj[cur][i].second;

            if(arr[cur]==2 && curk+1<=K){
                if(dist[viz][curk+1]>dist[cur][curk]+w/po[curk+1]){
                    ss.erase({dist[viz][curk+1], viz, curk+1});
                    dist[viz][curk+1]=dist[cur][curk]+w/po[curk+1];
                    ss.insert({dist[viz][curk+1], viz, curk+1});
                }
            }
            if(dist[viz][curk]>dist[cur][curk]+w/po[curk]){
                ss.erase({dist[viz][curk], viz, curk});
                dist[viz][curk]=dist[cur][curk]+w/po[curk];
                ss.insert({dist[viz][curk], viz, curk});
            }
        }
    }

    if(!achou[0][0])return -1;

    dfs(0, H);

    double ans=1e15;
    for(int i=0; i<N; i++){
        if(!visited[i] || (i!=0 && arr[i]!=0))continue;
        for(int j=0; j<=K; j++){
            ans=min(ans, dist[i][j]);
        }
    }

    if(ans<5e14)return ans;
    return -1;
}

Compilation message

cyberland.cpp: In function 'double solve(int, int, int, int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
cyberland.cpp:44:19: warning: narrowing conversion of 'H' from 'int' to 'double' [-Wnarrowing]
   44 |     ss.insert({0, H, 0});
      |                   ^
cyberland.cpp:64:50: warning: narrowing conversion of 'viz' from 'int' to 'double' [-Wnarrowing]
   64 |                     ss.erase({dist[viz][curk+1], viz, curk+1});
      |                                                  ^~~
cyberland.cpp:64:59: warning: narrowing conversion of '(curk + 1)' from 'int' to 'double' [-Wnarrowing]
   64 |                     ss.erase({dist[viz][curk+1], viz, curk+1});
      |                                                       ~~~~^~
cyberland.cpp:66:51: warning: narrowing conversion of 'viz' from 'int' to 'double' [-Wnarrowing]
   66 |                     ss.insert({dist[viz][curk+1], viz, curk+1});
      |                                                   ^~~
cyberland.cpp:66:60: warning: narrowing conversion of '(curk + 1)' from 'int' to 'double' [-Wnarrowing]
   66 |                     ss.insert({dist[viz][curk+1], viz, curk+1});
      |                                                        ~~~~^~
cyberland.cpp:70:44: warning: narrowing conversion of 'viz' from 'int' to 'double' [-Wnarrowing]
   70 |                 ss.erase({dist[viz][curk], viz, curk});
      |                                            ^~~
cyberland.cpp:70:49: warning: narrowing conversion of 'curk' from 'int' to 'double' [-Wnarrowing]
   70 |                 ss.erase({dist[viz][curk], viz, curk});
      |                                                 ^~~~
cyberland.cpp:72:45: warning: narrowing conversion of 'viz' from 'int' to 'double' [-Wnarrowing]
   72 |                 ss.insert({dist[viz][curk], viz, curk});
      |                                             ^~~
cyberland.cpp:72:50: warning: narrowing conversion of 'curk' from 'int' to 'double' [-Wnarrowing]
   72 |                 ss.insert({dist[viz][curk], viz, curk});
      |                                                  ^~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2016 ms 68940 KB Correct.
2 Correct 1976 ms 69192 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 69008 KB Correct.
2 Correct 76 ms 69004 KB Correct.
3 Correct 74 ms 68972 KB Correct.
4 Correct 74 ms 68956 KB Correct.
5 Correct 82 ms 68992 KB Correct.
6 Correct 58 ms 69588 KB Correct.
7 Correct 61 ms 69456 KB Correct.
8 Correct 46 ms 70152 KB Correct.
9 Correct 258 ms 68956 KB Correct.
10 Correct 247 ms 68756 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 69008 KB Correct.
2 Correct 74 ms 68964 KB Correct.
3 Correct 74 ms 68944 KB Correct.
4 Correct 251 ms 68948 KB Correct.
5 Correct 249 ms 68892 KB Correct.
6 Correct 37 ms 69364 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 328 ms 73076 KB Correct.
2 Correct 211 ms 69060 KB Correct.
3 Correct 197 ms 69128 KB Correct.
4 Correct 200 ms 69012 KB Correct.
5 Correct 393 ms 68960 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 68896 KB Correct.
2 Correct 73 ms 69072 KB Correct.
3 Correct 71 ms 69036 KB Correct.
4 Correct 58 ms 69784 KB Correct.
5 Correct 244 ms 68956 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 69336 KB Correct.
2 Correct 69 ms 68944 KB Correct.
3 Correct 67 ms 73908 KB Correct.
4 Correct 51 ms 69724 KB Correct.
5 Correct 250 ms 68952 KB Correct.
6 Correct 71 ms 68980 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 260 ms 69276 KB Correct.
2 Correct 66 ms 69204 KB Correct.
3 Correct 842 ms 76112 KB Correct.
4 Correct 380 ms 70404 KB Correct.
5 Correct 832 ms 75456 KB Correct.
6 Correct 397 ms 73716 KB Correct.
7 Correct 410 ms 70484 KB Correct.
8 Correct 380 ms 69292 KB Correct.
9 Correct 207 ms 69204 KB Correct.
10 Correct 199 ms 69200 KB Correct.
11 Correct 401 ms 69052 KB Correct.
12 Correct 249 ms 69204 KB Correct.
13 Correct 220 ms 69016 KB Correct.
14 Correct 388 ms 72528 KB Correct.
15 Correct 365 ms 69748 KB Correct.
16 Correct 217 ms 68944 KB Correct.
17 Correct 244 ms 69544 KB Correct.
18 Correct 212 ms 68944 KB Correct.
19 Correct 483 ms 69044 KB Correct.
20 Correct 60 ms 68948 KB Correct.
21 Correct 46 ms 68944 KB Correct.
22 Correct 56 ms 69552 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 334 ms 69080 KB Correct.
2 Correct 92 ms 69056 KB Correct.
3 Incorrect 1052 ms 79884 KB Wrong Answer.
4 Halted 0 ms 0 KB -