Submission #1191855

#	Time	Username	Problem	Language	Result	Execution time	Memory
1191855		Malix	Cyberland (APIO23_cyberland)	C++17	92 / 100	3099 ms	465912 KiB

cyberland

#include "cyberland.h"
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vii;
typedef pair<int,int> pi;
typedef vector<pi> pii;
typedef tuple<ll,ll,ll> ti;
typedef vector<ll> li;
typedef vector<li> lii;
 
#define REP(i,a,b) for(int i=a;i<b;i++)
#define F first
#define S second
#define PB push_back
#define LSOne(s) ((s)&(-s))
 
ll INF=1000000000000000010;
int inf=1e9+10;
ll M=1e9+7;

int n,m,h;
vector<vector<pi>> a;
vi b;
double dist[100000][50];

void dfs(int x){
    b[x]=1;
    if(x==h)return;
    for(auto u:a[x])if(b[u.F]==0)dfs(u.F);
}

double solve(int N, int M, int k, int H, std::vector<int> X, std::vector<int> Y, std::vector<int> C, std::vector<int> arr) {
    k=min(k,49);
    n=N;m=M;h=H;
    a.clear();a.resize(n);
    REP(i,0,m){
        a[X[i]].PB({Y[i],C[i]});
        a[Y[i]].PB({X[i],C[i]});
    }
    b.clear();b.resize(n,0);
    dfs(0);
    if(b[H]==0)return -1;
    REP(i,0,100000)REP(j,0,k+1)dist[i][j]=1e14+10;
    priority_queue<tuple<double,int,int>> pq;
    dist[H][0]=0;
    pq.push({0,H,0});
    while(!pq.empty()){
        double x=-get<0>(pq.top());
        int y=get<1>(pq.top());
        int z=get<2>(pq.top());
        pq.pop();
        if(dist[y][z]<x)continue;
        for(auto u:a[y])if(u.F!=H){
            if(arr[u.F]==2&&dist[u.F][min(z+1,k)]>x+(double)(u.S)/(1<<z)){
                dist[u.F][min(z+1,k)]=x+(double)(u.S)/(1<<z);
                pq.push({-dist[u.F][min(z+1,k)],u.F,min(z+1,k)});
            }
            else if(dist[u.F][z]>x+(double)(u.S)/(1<<z)){
                dist[u.F][z]=x+(double)(u.S)/(1<<z);
                pq.push({-dist[u.F][z],u.F,z});
            }
        }
    }
    double ans=1e14+10;
    REP(i,0,n)if(b[i]&&arr[i]==0)REP(j,0,k+1)ans=min(ans,dist[i][j]);
    REP(j,0,k+1)ans=min(ans,dist[0][j]);
    return ans;
}

• Subtask 1: 0 / 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