oj.uz

Submission #879135

# Submission time Handle Problem Language Result Execution time Memory
879135 2023-11-26T12:32:10 Z leanchec Cyberland (APIO23_cyberland) C++17
97 / 100
 3000 ms 82432 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){

    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]});
    }

    dfs(0, H);

    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<=min(K, 70); j++){
            dist[i][j]=1e15;
            achou[i][j]=false;
        }
    }

    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(cur==0 || arr[cur]==0 || curk==70){
            return dist[cur][curk];
        }

        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(!visited[viz])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});
                }
            }
            else 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});
            }
        }
    }
    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:46:19: warning: narrowing conversion of 'H' from 'int' to 'double' [-Wnarrowing]
   46 |     ss.insert({0, H, 0});
      |                   ^
cyberland.cpp:70:50: warning: narrowing conversion of 'viz' from 'int' to 'double' [-Wnarrowing]
   70 |                     ss.erase({dist[viz][curk+1], viz, curk+1});
      |                                                  ^~~
cyberland.cpp:70:59: warning: narrowing conversion of '(curk + 1)' from 'int' to 'double' [-Wnarrowing]
   70 |                     ss.erase({dist[viz][curk+1], viz, curk+1});
      |                                                       ~~~~^~
cyberland.cpp:72:51: warning: narrowing conversion of 'viz' from 'int' to 'double' [-Wnarrowing]
   72 |                     ss.insert({dist[viz][curk+1], viz, curk+1});
      |                                                   ^~~
cyberland.cpp:72:60: warning: narrowing conversion of '(curk + 1)' from 'int' to 'double' [-Wnarrowing]
   72 |                     ss.insert({dist[viz][curk+1], viz, curk+1});
      |                                                        ~~~~^~
cyberland.cpp:76:44: warning: narrowing conversion of 'viz' from 'int' to 'double' [-Wnarrowing]
   76 |                 ss.erase({dist[viz][curk], viz, curk});
      |                                            ^~~
cyberland.cpp:76:49: warning: narrowing conversion of 'curk' from 'int' to 'double' [-Wnarrowing]
   76 |                 ss.erase({dist[viz][curk], viz, curk});
      |                                                 ^~~~
cyberland.cpp:78:45: warning: narrowing conversion of 'viz' from 'int' to 'double' [-Wnarrowing]
   78 |                 ss.insert({dist[viz][curk], viz, curk});
      |                                             ^~~
cyberland.cpp:78:50: warning: narrowing conversion of 'curk' from 'int' to 'double' [-Wnarrowing]
   78 |                 ss.insert({dist[viz][curk], viz, curk});
      |                                                  ^~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2048 ms 69492 KB Correct.
2 Correct 2138 ms 69448 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 69712 KB Correct.
2 Correct 70 ms 70060 KB Correct.
3 Correct 69 ms 69972 KB Correct.
4 Correct 72 ms 69820 KB Correct.
5 Correct 69 ms 69968 KB Correct.
6 Correct 49 ms 70228 KB Correct.
7 Correct 62 ms 70740 KB Correct.
8 Correct 40 ms 70484 KB Correct.
9 Correct 251 ms 69716 KB Correct.
10 Correct 258 ms 69728 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 69716 KB Correct.
2 Correct 68 ms 69968 KB Correct.
3 Correct 71 ms 69732 KB Correct.
4 Correct 249 ms 69712 KB Correct.
5 Correct 251 ms 69828 KB Correct.
6 Correct 35 ms 69456 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 73044 KB Correct.
2 Correct 69 ms 69968 KB Correct.
3 Correct 66 ms 70004 KB Correct.
4 Correct 74 ms 70040 KB Correct.
5 Correct 256 ms 69840 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 69716 KB Correct.
2 Correct 72 ms 69972 KB Correct.
3 Correct 73 ms 70100 KB Correct.
4 Correct 54 ms 70844 KB Correct.
5 Correct 250 ms 69772 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 69768 KB Correct.
2 Correct 68 ms 69820 KB Correct.
3 Correct 68 ms 75856 KB Correct.
4 Correct 44 ms 70224 KB Correct.
5 Correct 250 ms 69716 KB Correct.
6 Correct 67 ms 69968 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 69892 KB Correct.
2 Correct 35 ms 69064 KB Correct.
3 Correct 78 ms 78088 KB Correct.
4 Correct 70 ms 72632 KB Correct.
5 Correct 64 ms 76144 KB Correct.
6 Correct 55 ms 74772 KB Correct.
7 Correct 71 ms 72684 KB Correct.
8 Correct 107 ms 71204 KB Correct.
9 Correct 68 ms 69976 KB Correct.
10 Correct 68 ms 69968 KB Correct.
11 Correct 170 ms 71072 KB Correct.
12 Correct 68 ms 69972 KB Correct.
13 Correct 68 ms 69972 KB Correct.
14 Correct 73 ms 74120 KB Correct.
15 Correct 76 ms 71764 KB Correct.
16 Correct 68 ms 70120 KB Correct.
17 Correct 70 ms 70148 KB Correct.
18 Correct 71 ms 69972 KB Correct.
19 Correct 88 ms 70952 KB Correct.
20 Correct 54 ms 68944 KB Correct.
21 Correct 35 ms 68968 KB Correct.
22 Correct 35 ms 69404 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 70016 KB Correct.
2 Correct 36 ms 69200 KB Correct.
3 Correct 107 ms 82432 KB Correct.
4 Correct 75 ms 71580 KB Correct.
5 Correct 64 ms 76236 KB Correct.
6 Correct 54 ms 74576 KB Correct.
7 Correct 69 ms 74324 KB Correct.
8 Correct 168 ms 70960 KB Correct.
9 Correct 68 ms 69972 KB Correct.
10 Correct 69 ms 69948 KB Correct.
11 Execution timed out 3057 ms 70248 KB Time limit exceeded
12 Halted 0 ms 0 KB -