oj.uz

Submission #777200

# Submission time Handle Problem Language Result Execution time Memory
777200 2023-07-08T18:59:29 Z groshi Cyberland (APIO23_cyberland) C++17
97 / 100
 3000 ms 93228 KB 
#include<bits/stdc++.h>
#include "cyberland.h"
using namespace std;
struct wi{
    vector<int> Q;
    double dp[71];
    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]=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 30 ms 33360 KB Correct.
2 Correct 31 ms 33384 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 28340 KB Correct.
2 Correct 44 ms 33880 KB Correct.
3 Correct 35 ms 32220 KB Correct.
4 Correct 36 ms 33356 KB Correct.
5 Correct 37 ms 33436 KB Correct.
6 Correct 30 ms 25516 KB Correct.
7 Correct 39 ms 33804 KB Correct.
8 Correct 17 ms 13140 KB Correct.
9 Correct 36 ms 33968 KB Correct.
10 Correct 35 ms 33356 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 32460 KB Correct.
2 Correct 36 ms 31764 KB Correct.
3 Correct 35 ms 29936 KB Correct.
4 Correct 38 ms 34196 KB Correct.
5 Correct 39 ms 34036 KB Correct.
6 Correct 7 ms 5720 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 187 ms 40896 KB Correct.
2 Correct 204 ms 32676 KB Correct.
3 Correct 175 ms 30116 KB Correct.
4 Correct 210 ms 31172 KB Correct.
5 Correct 173 ms 33472 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 31436 KB Correct.
2 Correct 40 ms 32516 KB Correct.
3 Correct 35 ms 32200 KB Correct.
4 Correct 32 ms 24916 KB Correct.
5 Correct 33 ms 33448 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 32460 KB Correct.
2 Correct 30 ms 28584 KB Correct.
3 Correct 61 ms 49860 KB Correct.
4 Correct 28 ms 23916 KB Correct.
5 Correct 38 ms 34244 KB Correct.
6 Correct 33 ms 29772 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 204 ms 29280 KB Correct.
2 Correct 27 ms 3952 KB Correct.
3 Correct 606 ms 66936 KB Correct.
4 Correct 478 ms 64052 KB Correct.
5 Correct 674 ms 59776 KB Correct.
6 Correct 337 ms 27148 KB Correct.
7 Correct 467 ms 62184 KB Correct.
8 Correct 466 ms 63088 KB Correct.
9 Correct 184 ms 29440 KB Correct.
10 Correct 183 ms 29904 KB Correct.
11 Correct 460 ms 63900 KB Correct.
12 Correct 190 ms 34448 KB Correct.
13 Correct 202 ms 30456 KB Correct.
14 Correct 392 ms 59844 KB Correct.
15 Correct 464 ms 58684 KB Correct.
16 Correct 181 ms 31796 KB Correct.
17 Correct 218 ms 32908 KB Correct.
18 Correct 215 ms 31676 KB Correct.
19 Correct 493 ms 62736 KB Correct.
20 Correct 14 ms 3336 KB Correct.
21 Correct 15 ms 3832 KB Correct.
22 Correct 26 ms 3400 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 698 ms 29228 KB Correct.
2 Correct 85 ms 6032 KB Correct.
3 Correct 534 ms 69996 KB Correct.
4 Correct 1045 ms 61120 KB Correct.
5 Correct 2455 ms 92608 KB Correct.
6 Correct 1323 ms 76420 KB Correct.
7 Correct 1139 ms 54372 KB Correct.
8 Correct 1232 ms 63844 KB Correct.
9 Correct 661 ms 29960 KB Correct.
10 Correct 654 ms 31212 KB Correct.
11 Correct 2510 ms 88140 KB Correct.
12 Correct 656 ms 35068 KB Correct.
13 Correct 740 ms 30772 KB Correct.
14 Execution timed out 3029 ms 93228 KB Time limit exceeded
15 Halted 0 ms 0 KB -