Submission #1310546

#	Time	Username	Problem	Language	Result	Execution time	Memory
1310546		StefanSebez	Cyberland (APIO23_cyberland)	C++20	100 / 100	1263 ms	115948 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,int>>pq[K+1];
    pq[K].push({-dist[K][0],0});
    for(int k=K;k>=0;k--){
        while(!pq[k].empty()){
            pair<ld,ll>temp=pq[k].top();pq[k].pop();
            int u=temp.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[k].push({0,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[k-1].push({-dist[k-1][i],i});
                }
                if(dist[k][i]>dist[k][u]+w){
                    dist[k][i]=dist[k][u]+w;
                    pq[k].push({-dist[k][i],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: 3 / 3