oj.uz

Submission #1093440

# Submission time Handle Problem Language Result Execution time Memory
1093440 2024-09-26T19:54:20 Z alexander707070 Cyberland (APIO23_cyberland) C++17
49 / 100
 665 ms 455384 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][81];
long double dist[MAXN][81];
long double ans;
bool vis[MAXN][81];
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,70);

    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 108 ms 191056 KB Correct.
2 Correct 109 ms 190928 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 140 ms 198224 KB Correct.
2 Correct 162 ms 198484 KB Correct.
3 Correct 155 ms 198252 KB Correct.
4 Correct 157 ms 198736 KB Correct.
5 Correct 152 ms 198484 KB Correct.
6 Correct 199 ms 239136 KB Correct.
7 Correct 221 ms 240072 KB Correct.
8 Correct 182 ms 271188 KB Correct.
9 Correct 145 ms 192436 KB Correct.
10 Correct 144 ms 192212 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 155 ms 198224 KB Correct.
2 Correct 155 ms 198484 KB Correct.
3 Correct 145 ms 198224 KB Correct.
4 Correct 145 ms 192340 KB Correct.
5 Correct 143 ms 192280 KB Correct.
6 Correct 124 ms 223736 KB Correct.

Subtask #4
0.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 520 ms 455384 KB Correct.
2 Incorrect 311 ms 197712 KB Wrong Answer.
3 Halted 0 ms 0 KB -

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 164 ms 203092 KB Correct.
2 Correct 153 ms 204608 KB Correct.
3 Correct 156 ms 203844 KB Correct.
4 Correct 240 ms 269392 KB Correct.
5 Correct 129 ms 192596 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 149 ms 203860 KB Correct.
2 Correct 144 ms 204116 KB Correct.
3 Correct 552 ms 417652 KB Correct.
4 Correct 166 ms 240464 KB Correct.
5 Correct 142 ms 192824 KB Correct.
6 Correct 147 ms 204880 KB Correct.

Subtask #7
0.0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 331 ms 209476 KB Wrong Answer.
2 Halted 0 ms 0 KB -

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Incorrect 665 ms 231104 KB Wrong Answer.
2 Halted 0 ms 0 KB -