Submission #777409

#	Time	Username	Problem	Language	Result	Execution time	Memory
777409		groshi	Cyberland (APIO23_cyberland)	C++17	97 / 100	3078 ms	121780 KiB

cyberland

#include<bits/stdc++.h>
#pragma GCC optimize "unroll-loops"
#pragma GCC optimize "O3"
#include "cyberland.h"
using namespace std;
vector<int> moge;
vector<int> Q[100010];
bool odw[100010];
vector<int> co;
void dfs(int x,int nie)
{
    odw[x]=1;
    if(x==nie)
        return;
    if(co[x]==0)
        moge.push_back(x);
    for(int i=0;i<Q[x].size();i+=2)
        if(odw[Q[x][i]]==0)
            dfs(Q[x][i],nie);
}
double solve(int n,int m,int k,int h,vector<int> x,vector<int> y,vector<int> c, vector<int> arr)
{
    for(int i=0;i<n;i++)
        Q[i].clear(),odw[i]=0;
    vector<double> dp[n+3];
    for(int i=0;i<m;i++)
    {
        Q[x[i]].push_back(y[i]);
        Q[y[i]].push_back(x[i]);
        Q[x[i]].push_back(c[i]);
        Q[y[i]].push_back(c[i]);
    }
    swap(arr,co);
    moge.clear();
    dfs(0,h);
    moge.push_back(0);
    priority_queue<pair<double,pair<int,int> > > kolejka;
    k=min(k,70);
    for(int i=0;i<n;i++)
        for(int j=0;j<=k;j++)
            dp[i].push_back(1e14);
    for(int i=0;i<moge.size();i++)
    {
        kolejka.push({0.0,{moge[i],0}});
        for(int j=0;j<=k;j++)
            dp[moge[i]][j]=0;
    }
    while(!kolejka.empty())
    {
        auto para=kolejka.top();
        kolejka.pop();
        int x=para.second.first;
        int typ=para.second.second;
        double ile=-para.first;
        if(ile>dp[x][typ])
            continue;
        if(x==h)
            continue;
        for(int i=0;i<Q[x].size();i+=2)
        {
            int pom=Q[x][i];
            double dodaj=Q[x][i+1];
            if(dp[pom][typ]>ile+dodaj)
                kolejka.push({-ile-dodaj,{pom,typ}}),dp[pom][typ]=ile+dodaj;
            if(co[pom]!=2)
                continue;
            dodaj+=ile;
            dodaj/=2;
            if(dp[pom][typ+1]>dodaj && typ+1<=k)
                kolejka.push({-dodaj,{pom,typ+1}}),dp[pom][typ+1]=dodaj;
        }
    }
    double minn=1e14;
    for(int i=0;i<=k;i++)
        minn=min(minn,dp[h][i]);
    if(minn==1e14)
        return -1;
    else return minn;
}

Compilation message (stderr)

cyberland.cpp: In function 'void dfs(int, int)':
cyberland.cpp:17:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |     for(int i=0;i<Q[x].size();i+=2)
      |                 ~^~~~~~~~~~~~
cyberland.cpp: In function 'double solve(int, int, int, int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
cyberland.cpp:42:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |     for(int i=0;i<moge.size();i++)
      |                 ~^~~~~~~~~~~~
cyberland.cpp:59:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |         for(int i=0;i<Q[x].size();i+=2)
      |                     ~^~~~~~~~~~~~

• 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