oj.uz

Submission #777173

# Submission time Handle Problem Language Result Execution time Memory
777173 2023-07-08T18:35:25 Z groshi Cyberland (APIO23_cyberland) C++17
97 / 100
 3000 ms 195104 KB 
#include<bits/stdc++.h>
#include "cyberland.h"
using namespace std;
struct wi{
    vector<int> Q;
    double dp[203];
    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,70);
    for(int i=0;i<n;i++)
        for(int j=0;j<=k;j++)
            w[i].dp[j]=1e18;
    for(int i=0;i<moge.size();i++)
        kolejka.push({0.0,{moge[i],0}}),w[moge[i]].dp[0]=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=1e18;
    for(int i=0;i<=k;i++)
        minn=min(minn,w[h].dp[i]);
    if(minn==1e18)
        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:55:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |         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 61 ms 90220 KB Correct.
2 Correct 49 ms 90144 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 74220 KB Correct.
2 Correct 52 ms 89188 KB Correct.
3 Correct 48 ms 84620 KB Correct.
4 Correct 50 ms 87792 KB Correct.
5 Correct 52 ms 88036 KB Correct.
6 Correct 43 ms 67028 KB Correct.
7 Correct 55 ms 89084 KB Correct.
8 Correct 25 ms 33380 KB Correct.
9 Correct 52 ms 90280 KB Correct.
10 Correct 50 ms 88768 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 85324 KB Correct.
2 Correct 58 ms 83696 KB Correct.
3 Correct 48 ms 78540 KB Correct.
4 Correct 52 ms 90956 KB Correct.
5 Correct 57 ms 90484 KB Correct.
6 Correct 11 ms 13924 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 244 ms 103160 KB Correct.
2 Correct 297 ms 86352 KB Correct.
3 Correct 264 ms 79552 KB Correct.
4 Correct 274 ms 82336 KB Correct.
5 Correct 246 ms 89552 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 83284 KB Correct.
2 Correct 49 ms 86064 KB Correct.
3 Correct 49 ms 85080 KB Correct.
4 Correct 43 ms 65176 KB Correct.
5 Correct 48 ms 89916 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 85896 KB Correct.
2 Correct 42 ms 75348 KB Correct.
3 Correct 86 ms 127996 KB Correct.
4 Correct 41 ms 63040 KB Correct.
5 Correct 54 ms 91468 KB Correct.
6 Correct 46 ms 78672 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 303 ms 77164 KB Correct.
2 Correct 40 ms 8900 KB Correct.
3 Correct 682 ms 168084 KB Correct.
4 Correct 542 ms 167056 KB Correct.
5 Correct 1049 ms 96708 KB Correct.
6 Correct 544 ms 54212 KB Correct.
7 Correct 516 ms 164024 KB Correct.
8 Correct 522 ms 166536 KB Correct.
9 Correct 262 ms 78292 KB Correct.
10 Correct 261 ms 79224 KB Correct.
11 Correct 525 ms 169036 KB Correct.
12 Correct 278 ms 92004 KB Correct.
13 Correct 295 ms 80880 KB Correct.
14 Correct 449 ms 153520 KB Correct.
15 Correct 504 ms 154936 KB Correct.
16 Correct 271 ms 83952 KB Correct.
17 Correct 329 ms 87112 KB Correct.
18 Correct 317 ms 84048 KB Correct.
19 Correct 762 ms 166908 KB Correct.
20 Correct 23 ms 8504 KB Correct.
21 Correct 22 ms 9160 KB Correct.
22 Correct 32 ms 4296 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 975 ms 76604 KB Correct.
2 Correct 126 ms 13392 KB Correct.
3 Correct 630 ms 173344 KB Correct.
4 Correct 1095 ms 161364 KB Correct.
5 Execution timed out 3047 ms 195104 KB Time limit exceeded
6 Halted 0 ms 0 KB -