oj.uz

Submission #777171

# Submission time Handle Problem Language Result Execution time Memory
777171 2023-07-08T18:31:21 Z groshi Cyberland (APIO23_cyberland) C++17
97 / 100
 3000 ms 264568 KB 
#include<bits/stdc++.h>
#include "cyberland.h"
#define int long long
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,80);
    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(long long int, long long int)':
cyberland.cpp:19:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |     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:43:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |     for(int i=0;i<moge.size();i++)
      |                 ~^~~~~~~~~~~~
cyberland.cpp:56:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |         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 52 ms 90740 KB Correct.
2 Correct 50 ms 90920 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 75516 KB Correct.
2 Correct 55 ms 90544 KB Correct.
3 Correct 51 ms 85980 KB Correct.
4 Correct 55 ms 89216 KB Correct.
5 Correct 55 ms 89512 KB Correct.
6 Correct 44 ms 68184 KB Correct.
7 Correct 58 ms 90492 KB Correct.
8 Correct 25 ms 34124 KB Correct.
9 Correct 54 ms 91720 KB Correct.
10 Correct 52 ms 90120 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 86776 KB Correct.
2 Correct 54 ms 84952 KB Correct.
3 Correct 50 ms 79864 KB Correct.
4 Correct 56 ms 92336 KB Correct.
5 Correct 55 ms 91960 KB Correct.
6 Correct 11 ms 14420 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 264 ms 107040 KB Correct.
2 Correct 329 ms 88404 KB Correct.
3 Correct 283 ms 81672 KB Correct.
4 Correct 302 ms 84500 KB Correct.
5 Correct 265 ms 91504 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 84564 KB Correct.
2 Correct 50 ms 87656 KB Correct.
3 Correct 50 ms 86576 KB Correct.
4 Correct 48 ms 66604 KB Correct.
5 Correct 50 ms 91340 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 87416 KB Correct.
2 Correct 45 ms 76788 KB Correct.
3 Correct 84 ms 130176 KB Correct.
4 Correct 38 ms 64224 KB Correct.
5 Correct 52 ms 92984 KB Correct.
6 Correct 48 ms 80104 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 328 ms 79440 KB Correct.
2 Correct 44 ms 10136 KB Correct.
3 Correct 735 ms 173580 KB Correct.
4 Correct 591 ms 171840 KB Correct.
5 Correct 1162 ms 116576 KB Correct.
6 Correct 541 ms 73984 KB Correct.
7 Correct 558 ms 168188 KB Correct.
8 Correct 571 ms 170488 KB Correct.
9 Correct 287 ms 80144 KB Correct.
10 Correct 285 ms 81348 KB Correct.
11 Correct 566 ms 173212 KB Correct.
12 Correct 320 ms 94268 KB Correct.
13 Correct 323 ms 82736 KB Correct.
14 Correct 462 ms 158820 KB Correct.
15 Correct 539 ms 159332 KB Correct.
16 Correct 290 ms 86412 KB Correct.
17 Correct 350 ms 89804 KB Correct.
18 Correct 340 ms 86508 KB Correct.
19 Correct 810 ms 171424 KB Correct.
20 Correct 25 ms 8748 KB Correct.
21 Correct 24 ms 9332 KB Correct.
22 Correct 40 ms 5684 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1274 ms 79392 KB Correct.
2 Correct 167 ms 18160 KB Correct.
3 Correct 759 ms 178168 KB Correct.
4 Correct 1306 ms 165724 KB Correct.
5 Execution timed out 3086 ms 264568 KB Time limit exceeded
6 Halted 0 ms 0 KB -