oj.uz

Submission #1093177

# Submission time Handle Problem Language Result Execution time Memory
1093177 2024-09-26T07:07:20 Z alexander707070 Cyberland (APIO23_cyberland) C++17
97 / 100
 2666 ms 448372 KB 
#include<bits/stdc++.h>
#define MAXN 100007
using namespace std;

const long double inf=1e15;

struct edge{
    int to,s;
    long double cost;

    inline friend bool operator < (edge fr,edge sc){
        return fr.cost>sc.cost;
    }
};

int n,m,k;
vector<edge> v[MAXN][31];
long double dist[MAXN][31];
long double ans;
bool vis[MAXN][31];
int ability[MAXN];

priority_queue<edge> q;

bool li[MAXN];

bool dfs(int x,int y){
    if(x==y)return true;

    li[x]=true;
    bool res=false;

    for(edge e:v[x][0]){
        if(li[e.to])continue;
        if(dfs(e.to,y))res=true;
    }

    return res;
}

long double gg(long double d,int a,int b){
    if(a>b)return d/2;
    return d;
}

void dijkstra(){

    while(!q.empty()){
        edge curr=q.top();
        q.pop();

        if(vis[curr.to][curr.s])continue;
        //vis[curr.to][curr.s]=true;

        for(edge e:v[curr.to][curr.s]){
            if(vis[e.to][e.s] or dist[e.to][e.s]<=gg(dist[curr.to][curr.s],curr.s,e.s)+e.cost)continue;

            dist[e.to][e.s]=gg(dist[curr.to][curr.s],curr.s,e.s)+e.cost;
            q.push({e.to,e.s,dist[e.to][e.s]});
        }
    }

}

void reset(){
    for(int i=1;i<=n;i++)li[i]=false;

    for(int i=1;i<=n;i++){
        for(int f=0;f<=k;f++){
            v[i][f].clear();
            vis[i][f]=false;
        }
    }
}

double solve(int N, int M, int K, int H, vector<int> X, vector<int> Y, vector<int> C, vector<int> arr){
    n=N; m=M; k=K; H++;
    k=min(k,30);

    reset();

    for(int i=1;i<=m;i++){
        X[i-1]++; Y[i-1]++;
        
        for(int f=0;f<=k;f++){
            if(X[i-1]!=H)v[X[i-1]][f].push_back({Y[i-1],f,C[i-1]});
            if(Y[i-1]!=H)v[Y[i-1]][f].push_back({X[i-1],f,C[i-1]});

            if(f>0 and arr[X[i-1]-1]==2 and X[i-1]!=H)v[X[i-1]][f].push_back({Y[i-1],f-1,C[i-1]});
            if(f>0 and arr[Y[i-1]-1]==2 and Y[i-1]!=H)v[Y[i-1]][f].push_back({X[i-1],f-1,C[i-1]});
        }
    }

    if(!dfs(1,H))return -1;

    for(int i=1;i<=n;i++){
        for(int f=0;f<=k;f++){
            dist[i][f]=inf;
        }
    }

    for(int i=1;i<=n;i++){
        ability[i]=arr[i-1];
        
        if((li[i] and ability[i]==0) or i==1){
            dist[i][k]=0;
            q.push({i,k,0});
        }
    }

    dijkstra();

    ans=dist[H][k];
    for(int i=0;i<=k;i++){
        ans=min(ans,dist[H][i]);
    }

    return ans;
}

/*int main(){

     cout<<solve(3,2,0,2,{0,1},{1,0},{5,4},{1,2,1})<<"\n";
    cout<<solve(3,2,0,2,{0,1},{1,2},{5,4},{1,2,1})<<"\n";
    cout<<solve(3, 2, 30, 2, {1, 2}, {2, 0}, {12, 4}, {1, 2, 1})<<"\n";
    cout<<solve(4, 4, 30, 3, {0, 0, 1, 2}, {1, 2, 3, 3}, {5, 4, 2, 4}, {1, 0, 2, 1})<<"\n";

    return 0;
}*/

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:86:66: warning: narrowing conversion of 'C.std::vector<int>::operator[](((std::vector<int>::size_type)(i - 1)))' from '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} to 'long double' [-Wnarrowing]
   86 |             if(X[i-1]!=H)v[X[i-1]][f].push_back({Y[i-1],f,C[i-1]});
      |                                                                  ^
cyberland.cpp:87:66: warning: narrowing conversion of 'C.std::vector<int>::operator[](((std::vector<int>::size_type)(i - 1)))' from '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} to 'long double' [-Wnarrowing]
   87 |             if(Y[i-1]!=H)v[Y[i-1]][f].push_back({X[i-1],f,C[i-1]});
      |                                                                  ^
cyberland.cpp:89:97: warning: narrowing conversion of 'C.std::vector<int>::operator[](((std::vector<int>::size_type)(i - 1)))' from '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} to 'long double' [-Wnarrowing]
   89 |             if(f>0 and arr[X[i-1]-1]==2 and X[i-1]!=H)v[X[i-1]][f].push_back({Y[i-1],f-1,C[i-1]});
      |                                                                                                 ^
cyberland.cpp:90:97: warning: narrowing conversion of 'C.std::vector<int>::operator[](((std::vector<int>::size_type)(i - 1)))' from '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} to 'long double' [-Wnarrowing]
   90 |             if(f>0 and arr[Y[i-1]-1]==2 and Y[i-1]!=H)v[Y[i-1]][f].push_back({X[i-1],f-1,C[i-1]});
      |                                                                                                 ^

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 73816 KB Correct.
2 Correct 47 ms 73944 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 79764 KB Correct.
2 Correct 97 ms 79704 KB Correct.
3 Correct 92 ms 79696 KB Correct.
4 Correct 96 ms 79952 KB Correct.
5 Correct 95 ms 79756 KB Correct.
6 Correct 130 ms 113236 KB Correct.
7 Correct 146 ms 114220 KB Correct.
8 Correct 122 ms 137612 KB Correct.
9 Correct 84 ms 74576 KB Correct.
10 Correct 85 ms 74620 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 79704 KB Correct.
2 Correct 96 ms 79604 KB Correct.
3 Correct 93 ms 79740 KB Correct.
4 Correct 87 ms 74600 KB Correct.
5 Correct 86 ms 74576 KB Correct.
6 Correct 61 ms 100244 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 613 ms 288704 KB Correct.
2 Correct 442 ms 79064 KB Correct.
3 Correct 395 ms 79052 KB Correct.
4 Correct 431 ms 79052 KB Correct.
5 Correct 327 ms 74284 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 84560 KB Correct.
2 Correct 95 ms 85844 KB Correct.
3 Correct 90 ms 85076 KB Correct.
4 Correct 163 ms 143260 KB Correct.
5 Correct 76 ms 74844 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 85124 KB Correct.
2 Correct 86 ms 85588 KB Correct.
3 Correct 489 ms 295368 KB Correct.
4 Correct 102 ms 118096 KB Correct.
5 Correct 75 ms 75088 KB Correct.
6 Correct 87 ms 86100 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 434 ms 91436 KB Correct.
2 Correct 102 ms 91856 KB Correct.
3 Correct 1280 ms 281796 KB Correct.
4 Correct 989 ms 145096 KB Correct.
5 Correct 2666 ms 448372 KB Correct.
6 Correct 1586 ms 391892 KB Correct.
7 Correct 899 ms 145616 KB Correct.
8 Correct 768 ms 89552 KB Correct.
9 Correct 392 ms 92100 KB Correct.
10 Correct 374 ms 93376 KB Correct.
11 Correct 715 ms 81352 KB Correct.
12 Correct 431 ms 92028 KB Correct.
13 Correct 465 ms 91716 KB Correct.
14 Correct 837 ms 173548 KB Correct.
15 Correct 805 ms 111300 KB Correct.
16 Correct 410 ms 91332 KB Correct.
17 Correct 480 ms 92112 KB Correct.
18 Correct 418 ms 91236 KB Correct.
19 Correct 916 ms 90284 KB Correct.
20 Correct 50 ms 75724 KB Correct.
21 Correct 50 ms 79560 KB Correct.
22 Correct 117 ms 111296 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 432 ms 92612 KB Correct.
2 Correct 106 ms 92108 KB Correct.
3 Incorrect 1175 ms 378192 KB Wrong Answer.
4 Halted 0 ms 0 KB -