oj.uz

Submission #777202

# Submission time Handle Problem Language Result Execution time Memory
777202 2023-07-08T19:00:52 Z groshi Cyberland (APIO23_cyberland) C++17
97 / 100
 681 ms 62160 KB 
#include<bits/stdc++.h>
#include "cyberland.h"
using namespace std;
struct wi{
    vector<int> Q;
    double dp[61];
    int co;
    int odw=0;
}*w;
vector<int> moge;
void dfs(int x,int nie)
{
    w[x].odw=1;
    if(x==nie)
        return;
    if(w[x].co==0)
        moge.push_back(x);
    for(int i=0;i<w[x].Q.size();i+=2)
        if(w[w[x].Q[i]].odw==0)
            dfs(w[x].Q[i],nie);
}
double solve(int32_t n,int32_t m,int32_t k,int32_t h,vector<int32_t> x,vector<int32_t> y,vector<int32_t> c, vector<int32_t> arr)
{
    w=new wi[n+3];
    for(int i=0;i<m;i++)
    {
        w[x[i]].Q.push_back(y[i]);
        w[y[i]].Q.push_back(x[i]);
        w[x[i]].Q.push_back(c[i]);
        w[y[i]].Q.push_back(c[i]);
    }
    for(int i=0;i<n;i++)
        w[i].co=arr[i];
    moge.clear();
    dfs(0,h);
    moge.push_back(0);
    priority_queue<pair<double,pair<int,int> > > kolejka;
    k=min(k,60);
    for(int i=0;i<n;i++)
        for(int j=0;j<=k;j++)
            w[i].dp[j]=1e14;
    for(int i=0;i<moge.size();i++)
    {
        kolejka.push({0.0,{moge[i],0}});
        for(int j=0;j<=k;j++)
            w[moge[i]].dp[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>w[x].dp[typ])
            continue;
        if(x==h)
            continue;
        for(int i=0;i<w[x].Q.size();i+=2)
        {
            int pom=w[x].Q[i];
            double dodaj=w[x].Q[i+1];
            if(w[pom].dp[typ]>ile+dodaj)
                kolejka.push({-ile-dodaj,{pom,typ}}),w[pom].dp[typ]=ile+dodaj;
            if(w[pom].co!=2)
                continue;
            dodaj+=ile;
            dodaj/=2;
            if(w[pom].dp[typ+1]>dodaj && typ+1<=k)
                kolejka.push({-dodaj,{pom,typ+1}}),w[pom].dp[typ+1]=dodaj;
        }
    }
    double minn=1e14;
    for(int i=0;i<=k;i++)
        minn=min(minn,w[h].dp[i]);
    if(minn==1e14)
        return -1;
    else return minn;
}

Compilation message

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

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 29104 KB Correct.
2 Correct 26 ms 29048 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 24788 KB Correct.
2 Correct 34 ms 29684 KB Correct.
3 Correct 33 ms 28148 KB Correct.
4 Correct 33 ms 29260 KB Correct.
5 Correct 34 ms 29364 KB Correct.
6 Correct 27 ms 22356 KB Correct.
7 Correct 36 ms 29632 KB Correct.
8 Correct 15 ms 11616 KB Correct.
9 Correct 31 ms 29672 KB Correct.
10 Correct 32 ms 29268 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 28452 KB Correct.
2 Correct 35 ms 27860 KB Correct.
3 Correct 33 ms 26276 KB Correct.
4 Correct 36 ms 29900 KB Correct.
5 Correct 35 ms 29780 KB Correct.
6 Correct 7 ms 5076 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 156 ms 36412 KB Correct.
2 Correct 202 ms 28500 KB Correct.
3 Correct 173 ms 26440 KB Correct.
4 Correct 182 ms 27296 KB Correct.
5 Correct 161 ms 29260 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 27456 KB Correct.
2 Correct 36 ms 28564 KB Correct.
3 Correct 32 ms 28196 KB Correct.
4 Correct 28 ms 21972 KB Correct.
5 Correct 32 ms 29320 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 28364 KB Correct.
2 Correct 28 ms 24972 KB Correct.
3 Correct 55 ms 43836 KB Correct.
4 Correct 21 ms 20948 KB Correct.
5 Correct 32 ms 29888 KB Correct.
6 Correct 30 ms 26076 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 200 ms 25620 KB Correct.
2 Correct 26 ms 3604 KB Correct.
3 Correct 593 ms 59200 KB Correct.
4 Correct 470 ms 56064 KB Correct.
5 Correct 681 ms 57240 KB Correct.
6 Correct 337 ms 26456 KB Correct.
7 Correct 456 ms 54420 KB Correct.
8 Correct 468 ms 55236 KB Correct.
9 Correct 181 ms 25856 KB Correct.
10 Correct 180 ms 26156 KB Correct.
11 Correct 453 ms 56072 KB Correct.
12 Correct 189 ms 30036 KB Correct.
13 Correct 208 ms 26896 KB Correct.
14 Correct 391 ms 52740 KB Correct.
15 Correct 459 ms 51580 KB Correct.
16 Correct 180 ms 27912 KB Correct.
17 Correct 212 ms 28800 KB Correct.
18 Correct 216 ms 27756 KB Correct.
19 Correct 497 ms 55036 KB Correct.
20 Correct 14 ms 2948 KB Correct.
21 Correct 15 ms 3232 KB Correct.
22 Correct 26 ms 3400 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 555 ms 25652 KB Correct.
2 Correct 69 ms 5676 KB Correct.
3 Incorrect 454 ms 62160 KB Wrong Answer.
4 Halted 0 ms 0 KB -