oj.uz

Submission #1093176

# Submission time Handle Problem Language Result Execution time Memory
1093176 2024-09-26T07:06:28 Z alexander707070 Cyberland (APIO23_cyberland) C++17
97 / 100
 3000 ms 2097152 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++;

    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:85: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]
   85 |             if(X[i-1]!=H)v[X[i-1]][f].push_back({Y[i-1],f,C[i-1]});
      |                                                                  ^
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(Y[i-1]!=H)v[Y[i-1]][f].push_back({X[i-1],f,C[i-1]});
      |                                                                  ^
cyberland.cpp:88: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]
   88 |             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: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[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 45 ms 74076 KB Correct.
2 Correct 45 ms 74232 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 80516 KB Correct.
2 Correct 92 ms 79704 KB Correct.
3 Correct 89 ms 79672 KB Correct.
4 Correct 93 ms 79948 KB Correct.
5 Correct 93 ms 79700 KB Correct.
6 Correct 122 ms 113232 KB Correct.
7 Correct 148 ms 114260 KB Correct.
8 Correct 114 ms 137608 KB Correct.
9 Correct 80 ms 74584 KB Correct.
10 Correct 81 ms 74584 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 80724 KB Correct.
2 Correct 95 ms 80648 KB Correct.
3 Correct 86 ms 80496 KB Correct.
4 Correct 82 ms 75484 KB Correct.
5 Correct 81 ms 75344 KB Correct.
6 Correct 62 ms 100216 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 630 ms 290024 KB Correct.
2 Correct 451 ms 80092 KB Correct.
3 Correct 401 ms 80080 KB Correct.
4 Correct 413 ms 79820 KB Correct.
5 Correct 328 ms 75348 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 85388 KB Correct.
2 Correct 94 ms 86872 KB Correct.
3 Correct 94 ms 86100 KB Correct.
4 Correct 165 ms 144108 KB Correct.
5 Correct 69 ms 75860 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 101 ms 86096 KB Correct.
2 Correct 82 ms 86612 KB Correct.
3 Correct 481 ms 297000 KB Correct.
4 Correct 102 ms 118868 KB Correct.
5 Correct 75 ms 75932 KB Correct.
6 Correct 92 ms 87064 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 432 ms 92612 KB Correct.
2 Correct 100 ms 92108 KB Correct.
3 Correct 1374 ms 284312 KB Correct.
4 Correct 1014 ms 147400 KB Correct.
5 Correct 2656 ms 450068 KB Correct.
6 Correct 1449 ms 393368 KB Correct.
7 Correct 868 ms 147916 KB Correct.
8 Correct 752 ms 91600 KB Correct.
9 Correct 394 ms 92864 KB Correct.
10 Correct 379 ms 94400 KB Correct.
11 Correct 708 ms 83216 KB Correct.
12 Correct 440 ms 92964 KB Correct.
13 Correct 464 ms 92748 KB Correct.
14 Correct 829 ms 175816 KB Correct.
15 Correct 810 ms 113504 KB Correct.
16 Correct 403 ms 92356 KB Correct.
17 Correct 491 ms 93088 KB Correct.
18 Correct 434 ms 92368 KB Correct.
19 Correct 947 ms 92232 KB Correct.
20 Correct 48 ms 75468 KB Correct.
21 Correct 51 ms 79560 KB Correct.
22 Correct 125 ms 111428 KB Correct.

Subtask #8
0.0 / 3.0

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