oj.uz

Submission #1093439

# Submission time Handle Problem Language Result Execution time Memory
1093439 2024-09-26T19:53:06 Z alexander707070 Cyberland (APIO23_cyberland) C++17
97 / 100
 3000 ms 1163960 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 191120 KB Correct.
2 Correct 111 ms 191056 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 150 ms 198228 KB Correct.
2 Correct 152 ms 198488 KB Correct.
3 Correct 161 ms 198352 KB Correct.
4 Correct 158 ms 198520 KB Correct.
5 Correct 155 ms 198464 KB Correct.
6 Correct 210 ms 239188 KB Correct.
7 Correct 223 ms 240208 KB Correct.
8 Correct 188 ms 271332 KB Correct.
9 Correct 143 ms 192452 KB Correct.
10 Correct 142 ms 192304 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 154 ms 198348 KB Correct.
2 Correct 160 ms 198484 KB Correct.
3 Correct 151 ms 198500 KB Correct.
4 Correct 144 ms 192340 KB Correct.
5 Correct 144 ms 192340 KB Correct.
6 Correct 128 ms 223824 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 680 ms 455428 KB Correct.
2 Correct 548 ms 197608 KB Correct.
3 Correct 456 ms 197584 KB Correct.
4 Correct 474 ms 197580 KB Correct.
5 Correct 393 ms 192248 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 150 ms 202996 KB Correct.
2 Correct 157 ms 204624 KB Correct.
3 Correct 156 ms 203724 KB Correct.
4 Correct 234 ms 269140 KB Correct.
5 Correct 132 ms 192596 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 161 ms 203784 KB Correct.
2 Correct 148 ms 204112 KB Correct.
3 Correct 558 ms 417624 KB Correct.
4 Correct 179 ms 240468 KB Correct.
5 Correct 141 ms 192948 KB Correct.
6 Correct 151 ms 204880 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 503 ms 210116 KB Correct.
2 Correct 166 ms 209644 KB Correct.
3 Correct 1363 ms 479980 KB Correct.
4 Correct 1061 ms 282316 KB Correct.
5 Correct 2717 ms 596584 KB Correct.
6 Correct 1528 ms 518852 KB Correct.
7 Correct 991 ms 284364 KB Correct.
8 Correct 872 ms 211408 KB Correct.
9 Correct 452 ms 210628 KB Correct.
10 Correct 444 ms 211900 KB Correct.
11 Correct 799 ms 201028 KB Correct.
12 Correct 494 ms 210632 KB Correct.
13 Correct 546 ms 210364 KB Correct.
14 Correct 1012 ms 331140 KB Correct.
15 Correct 911 ms 240668 KB Correct.
16 Correct 474 ms 209860 KB Correct.
17 Correct 565 ms 210744 KB Correct.
18 Correct 489 ms 209868 KB Correct.
19 Correct 1002 ms 209996 KB Correct.
20 Correct 113 ms 192460 KB Correct.
21 Correct 113 ms 196812 KB Correct.
22 Correct 181 ms 228884 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1568 ms 234164 KB Correct.
2 Correct 342 ms 231092 KB Correct.
3 Correct 2029 ms 891860 KB Correct.
4 Correct 1972 ms 249536 KB Correct.
5 Execution timed out 3123 ms 1163960 KB Time limit exceeded
6 Halted 0 ms 0 KB -