Submission #1283254

#	Time	Username	Problem	Language	Result	Execution time	Memory
1283254		StefanSebez	Cyberland (APIO23_cyberland)	C++20	97 / 100	3095 ms	115992 KiB

cyberland

#include "cyberland.h"
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define ll long long
#define ld long double
#pragma GCC optimize("ofast")
#pragma GCC optimize("unroll-loops")
const int N=1e5+50,M=66;
const ll INF=1e18;
vector<pair<int,ll>>E[N];
int n,m;
vector<int>a;
void chmn(ll &x,ll y){x=min(x,y);}
bool chmn(ld &x,ld y){bool bul=false;if(x>y)bul=true;x=min(x,y);return bul;}
ld dist[M+1][N];
double solve(int n1, int m1, int K, int H, std::vector<int> x, std::vector<int> y, std::vector<int> c, std::vector<int> arr) {
	K=min(K,M);
    n=n1,m=m1;a=arr;
    for(int i=0;i<m;i++){
        E[x[i]].pb({y[i],(ll)c[i]});
        E[y[i]].pb({x[i],(ll)c[i]});
    }
    for(int k=0;k<=K;k++){
        for(int i=0;i<n;i++){
            dist[k][i]=INF;
        }
        dist[k][0]=0;
    }
    priority_queue<pair<ld,pair<ll,ll>>>pq;
    pq.push({-dist[K][0],{K,0}});
    while(!pq.empty()){
        pair<ld,pair<ll,ll>>temp=pq.top();pq.pop();
        int k=temp.se.fi,u=temp.se.se;ld W=-temp.fi;
        if(W>dist[k][u]) continue;
        if(u==H) continue;
        for(auto [i,w]:E[u]){
            if(a[i]==0&&dist[k][i]>0){
                //if(chmn(dist[k][i],(ld)0)) pq.push({-dist[k][i],{k,i}});
                pq.push({0,{k,i}});dist[k][i]=0;
            }
            else if(k>0&&a[i]==2&&2*dist[k-1][i]>dist[k][u]+w){
                dist[k-1][i]=(dist[k][u]+w)/2;
                pq.push({-dist[k-1][i],{k-1,i}});
            }
            if(dist[k][i]>dist[k][u]+w){
                dist[k][i]=dist[k][u]+w;
                pq.push({-dist[k][i],{k,i}});
            }
        }
    }
    ld res=INF;for(int k=0;k<=K;k++) res=min(res,dist[k][H]);

    for(int i=0;i<=n;i++){
        E[i].clear();
        for(int k=0;k<=K;k++){
            dist[k][i]=0;
        }
    }
    a.clear();

    if(res>=INF) return (ld)-1;
    return res;
}

Compilation message (stderr)

cyberland.cpp:9:29: warning: bad option '-fofast' to pragma 'optimize' [-Wpragmas]
    9 | #pragma GCC optimize("ofast")
      |                             ^
cyberland.cpp:16:21: warning: bad option '-fofast' to attribute 'optimize' [-Wattributes]
   16 | void chmn(ll &x,ll y){x=min(x,y);}
      |                     ^
cyberland.cpp:17:21: warning: bad option '-fofast' to attribute 'optimize' [-Wattributes]
   17 | bool chmn(ld &x,ld y){bool bul=false;if(x>y)bul=true;x=min(x,y);return bul;}
      |                     ^
cyberland.cpp:19:124: warning: bad option '-fofast' to attribute 'optimize' [-Wattributes]
   19 | double solve(int n1, int m1, int K, int H, std::vector<int> x, std::vector<int> y, std::vector<int> c, std::vector<int> arr) {
      |                                                                                                                            ^

• Subtask 1: 5 / 5
• Subtask 2: 8 / 8
• Subtask 3: 13 / 13
• Subtask 4: 19 / 19
• Subtask 5: 7 / 7
• Subtask 6: 16 / 16
• Subtask 7: 29 / 29
• Subtask 8: 0 / 3