oj.uz

Submission #777192

# Submission time Handle Problem Language Result Execution time Memory
777192 2023-07-08T18:54:38 Z groshi Cyberland (APIO23_cyberland) C++17
97 / 100
 3000 ms 237888 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}});
        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=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: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 49 ms 90324 KB Correct.
2 Correct 50 ms 90428 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 74708 KB Correct.
2 Correct 60 ms 89980 KB Correct.
3 Correct 52 ms 85452 KB Correct.
4 Correct 54 ms 88568 KB Correct.
5 Correct 54 ms 88836 KB Correct.
6 Correct 50 ms 67784 KB Correct.
7 Correct 59 ms 89852 KB Correct.
8 Correct 33 ms 33740 KB Correct.
9 Correct 64 ms 90924 KB Correct.
10 Correct 51 ms 89356 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 86064 KB Correct.
2 Correct 53 ms 84312 KB Correct.
3 Correct 50 ms 79324 KB Correct.
4 Correct 53 ms 91340 KB Correct.
5 Correct 56 ms 91180 KB Correct.
6 Correct 11 ms 14164 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 182 ms 101840 KB Correct.
2 Correct 245 ms 86984 KB Correct.
3 Correct 190 ms 80388 KB Correct.
4 Correct 202 ms 83104 KB Correct.
5 Correct 212 ms 90096 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 83988 KB Correct.
2 Correct 52 ms 86744 KB Correct.
3 Correct 53 ms 85840 KB Correct.
4 Correct 45 ms 65896 KB Correct.
5 Correct 52 ms 90460 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 86604 KB Correct.
2 Correct 45 ms 75988 KB Correct.
3 Correct 89 ms 128704 KB Correct.
4 Correct 37 ms 63508 KB Correct.
5 Correct 52 ms 92188 KB Correct.
6 Correct 47 ms 79048 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 223 ms 77636 KB Correct.
2 Correct 28 ms 8336 KB Correct.
3 Correct 723 ms 168832 KB Correct.
4 Correct 529 ms 167780 KB Correct.
5 Correct 724 ms 97344 KB Correct.
6 Correct 346 ms 38544 KB Correct.
7 Correct 519 ms 164576 KB Correct.
8 Correct 496 ms 167188 KB Correct.
9 Correct 200 ms 78604 KB Correct.
10 Correct 200 ms 79856 KB Correct.
11 Correct 495 ms 169608 KB Correct.
12 Correct 205 ms 92732 KB Correct.
13 Correct 221 ms 81476 KB Correct.
14 Correct 453 ms 154060 KB Correct.
15 Correct 494 ms 155480 KB Correct.
16 Correct 196 ms 84220 KB Correct.
17 Correct 245 ms 87756 KB Correct.
18 Correct 233 ms 84692 KB Correct.
19 Correct 530 ms 167032 KB Correct.
20 Correct 17 ms 8584 KB Correct.
21 Correct 17 ms 9208 KB Correct.
22 Correct 27 ms 4424 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 734 ms 77224 KB Correct.
2 Correct 87 ms 10364 KB Correct.
3 Correct 648 ms 173656 KB Correct.
4 Correct 1085 ms 161636 KB Correct.
5 Correct 2499 ms 130020 KB Correct.
6 Correct 1389 ms 88024 KB Correct.
7 Correct 1208 ms 140708 KB Correct.
8 Correct 1269 ms 170120 KB Correct.
9 Correct 679 ms 79112 KB Correct.
10 Correct 698 ms 80296 KB Correct.
11 Correct 2595 ms 237888 KB Correct.
12 Correct 701 ms 92496 KB Correct.
13 Correct 794 ms 81440 KB Correct.
14 Execution timed out 3072 ms 133532 KB Time limit exceeded
15 Halted 0 ms 0 KB -