oj.uz

Submission #777209

# Submission time Handle Problem Language Result Execution time Memory
777209 2023-07-08T19:07:13 Z groshi Cyberland (APIO23_cyberland) C++17
97 / 100
 671 ms 62544 KB 
#include<bits/stdc++.h>
#pragma GCC optimize "Ofast"
#pragma GCC optimize "unroll-loops"
#pragma GCC optimize "O3"
#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:21:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |     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:45:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |     for(int i=0;i<moge.size();i++)
      |                 ~^~~~~~~~~~~~
cyberland.cpp:62:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |         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 28 ms 29132 KB Correct.
2 Correct 30 ms 29172 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 24852 KB Correct.
2 Correct 37 ms 30000 KB Correct.
3 Correct 36 ms 28492 KB Correct.
4 Correct 39 ms 29456 KB Correct.
5 Correct 38 ms 29580 KB Correct.
6 Correct 30 ms 22600 KB Correct.
7 Correct 38 ms 29956 KB Correct.
8 Correct 16 ms 11784 KB Correct.
9 Correct 35 ms 29924 KB Correct.
10 Correct 35 ms 29496 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 28624 KB Correct.
2 Correct 35 ms 28184 KB Correct.
3 Correct 35 ms 26448 KB Correct.
4 Correct 37 ms 30020 KB Correct.
5 Correct 37 ms 29976 KB Correct.
6 Correct 7 ms 5200 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 157 ms 36784 KB Correct.
2 Correct 232 ms 28824 KB Correct.
3 Correct 176 ms 26752 KB Correct.
4 Correct 189 ms 27580 KB Correct.
5 Correct 163 ms 29536 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 27692 KB Correct.
2 Correct 34 ms 28860 KB Correct.
3 Correct 38 ms 28568 KB Correct.
4 Correct 31 ms 22128 KB Correct.
5 Correct 31 ms 29496 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 28660 KB Correct.
2 Correct 29 ms 25212 KB Correct.
3 Correct 55 ms 44312 KB Correct.
4 Correct 23 ms 21196 KB Correct.
5 Correct 34 ms 30156 KB Correct.
6 Correct 33 ms 26356 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 200 ms 25948 KB Correct.
2 Correct 26 ms 3732 KB Correct.
3 Correct 623 ms 59756 KB Correct.
4 Correct 482 ms 56440 KB Correct.
5 Correct 671 ms 57328 KB Correct.
6 Correct 335 ms 26700 KB Correct.
7 Correct 462 ms 54688 KB Correct.
8 Correct 468 ms 55548 KB Correct.
9 Correct 182 ms 26112 KB Correct.
10 Correct 186 ms 26544 KB Correct.
11 Correct 451 ms 56180 KB Correct.
12 Correct 191 ms 30452 KB Correct.
13 Correct 202 ms 26892 KB Correct.
14 Correct 423 ms 53088 KB Correct.
15 Correct 460 ms 51788 KB Correct.
16 Correct 194 ms 28084 KB Correct.
17 Correct 217 ms 29300 KB Correct.
18 Correct 216 ms 28000 KB Correct.
19 Correct 484 ms 55424 KB Correct.
20 Correct 14 ms 3076 KB Correct.
21 Correct 16 ms 3352 KB Correct.
22 Correct 26 ms 3460 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 564 ms 25896 KB Correct.
2 Correct 69 ms 5796 KB Correct.
3 Incorrect 448 ms 62544 KB Wrong Answer.
4 Halted 0 ms 0 KB -