Submission #969034

#	Time	Username	Problem	Language	Result	Execution time	Memory
969034		kshitiz101	Cyberland (APIO23_cyberland)	C++17	40 / 100	3048 ms	39264 KiB

cyberland

#include<bits/stdc++.h>
#include "cyberland.h"
using namespace std;
 
 
#define ll long long
#define ld long double
#define endl "\n"
#define yes cout<<"YES"<<endl
#define no  cout<<"NO"<<endl
const int N=1e5+10;
vector<pair<ll,ll>> adj[N];
ld ans[N][31];
ll n,m,h,k;
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)
{
     n=N;
     m=M;
     k=K;
     h=H;
     vector<ll> first,second,third;
     for(int i=0;i<m;i++)
     first.push_back(x[i]);
     
     for(int i=0;i<m;i++)
     second.push_back(y[i]);
     
     for(int i=0;i<m;i++)
     third.push_back(c[i]);
     
     ll type[n];
     for(int i=0;i<n;i++)
     type[i]=arr[i];
     
     for(int i=0;i<m;i++)
     {
          adj[first[i]].push_back({second[i],third[i]});
          adj[second[i]].push_back({first[i],third[i]});
     }
     
     priority_queue<tuple<ld,ll,ll>,vector<tuple<ld,ll,ll>>,greater<tuple<ld,ll,ll>>> pq;
     pq.push({0.0,0,0});
     
     for(int i=1;i<n;i++)
     {
          for(int j=0;j<=k;j++)
          ans[i][j]=1e15;
     }
     
     while(pq.size())
     {
          auto it=pq.top();
          pq.pop();
          ld dist=get<0>(it);
          ll node=get<1>(it);
          ll usedk=get<2>(it);
          
          if(ans[node][usedk]<dist||node==h)
          continue;
          
          for(auto &p:adj[node])
          {
               ld e=dist+(long double)p.second;
               if(type[p.first]==0)
               e=0;
               
               if(usedk<k&&type[p.first]==2)
               {
                    if(ans[p.first][usedk]>e)
                    {
                         ans[p.first][usedk]=e;
                         pq.push({e,p.first,usedk});
                    }
                    
                    if(ans[p.first][usedk+1]>(e/2.0))
                    {
                         ans[p.first][usedk+1]=(e/2.0);
                         pq.push({e/2.0,p.first,usedk+1});
                    }
               }
               else
               {
                    if(ans[p.first][usedk]>e)
                    {
                         ans[p.first][usedk]=e;
                         pq.push({e,p.first,usedk});
                    }
               }
          }
     }
     
     ld final=1e15;
     for(int i=0;i<=k;i++)
     final=min(final,ans[h][i]);
     
     for(int i=0;i<n;i++)
     {
          for(int j=0;j<=k;j++)
          ans[i][j]=0;
          adj[i].clear();
     }
     
     return final;
}

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