oj.uz

Submission #777211

# Submission time Handle Problem Language Result Execution time Memory
777211 2023-07-08T19:08:04 Z groshi Cyberland (APIO23_cyberland) C++17
97 / 100
 3000 ms 93604 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[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: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 36 ms 33536 KB Correct.
2 Correct 28 ms 33700 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 28552 KB Correct.
2 Correct 49 ms 34180 KB Correct.
3 Correct 37 ms 32428 KB Correct.
4 Correct 36 ms 33572 KB Correct.
5 Correct 37 ms 33692 KB Correct.
6 Correct 31 ms 25776 KB Correct.
7 Correct 40 ms 34176 KB Correct.
8 Correct 18 ms 13420 KB Correct.
9 Correct 37 ms 34212 KB Correct.
10 Correct 36 ms 33564 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 32716 KB Correct.
2 Correct 45 ms 32112 KB Correct.
3 Correct 39 ms 30132 KB Correct.
4 Correct 38 ms 34376 KB Correct.
5 Correct 42 ms 34236 KB Correct.
6 Correct 7 ms 5844 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 161 ms 41184 KB Correct.
2 Correct 205 ms 32920 KB Correct.
3 Correct 186 ms 30424 KB Correct.
4 Correct 185 ms 31436 KB Correct.
5 Correct 164 ms 33688 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 31668 KB Correct.
2 Correct 42 ms 32784 KB Correct.
3 Correct 33 ms 32456 KB Correct.
4 Correct 33 ms 25168 KB Correct.
5 Correct 37 ms 33776 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 32668 KB Correct.
2 Correct 33 ms 28736 KB Correct.
3 Correct 61 ms 50168 KB Correct.
4 Correct 26 ms 24188 KB Correct.
5 Correct 36 ms 34380 KB Correct.
6 Correct 47 ms 30096 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 209 ms 29592 KB Correct.
2 Correct 33 ms 4004 KB Correct.
3 Correct 618 ms 67376 KB Correct.
4 Correct 491 ms 64372 KB Correct.
5 Correct 712 ms 60144 KB Correct.
6 Correct 391 ms 27560 KB Correct.
7 Correct 477 ms 62536 KB Correct.
8 Correct 508 ms 63472 KB Correct.
9 Correct 186 ms 29860 KB Correct.
10 Correct 193 ms 30300 KB Correct.
11 Correct 464 ms 64300 KB Correct.
12 Correct 189 ms 34684 KB Correct.
13 Correct 217 ms 30844 KB Correct.
14 Correct 399 ms 60184 KB Correct.
15 Correct 494 ms 59096 KB Correct.
16 Correct 181 ms 32212 KB Correct.
17 Correct 225 ms 33276 KB Correct.
18 Correct 215 ms 32088 KB Correct.
19 Correct 527 ms 63008 KB Correct.
20 Correct 15 ms 3444 KB Correct.
21 Correct 15 ms 3876 KB Correct.
22 Correct 26 ms 3536 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 709 ms 29556 KB Correct.
2 Correct 95 ms 6108 KB Correct.
3 Correct 552 ms 70460 KB Correct.
4 Correct 1077 ms 61848 KB Correct.
5 Correct 2554 ms 93108 KB Correct.
6 Correct 1400 ms 76772 KB Correct.
7 Correct 1187 ms 54900 KB Correct.
8 Correct 1239 ms 64236 KB Correct.
9 Correct 661 ms 30312 KB Correct.
10 Correct 663 ms 31560 KB Correct.
11 Correct 2506 ms 88552 KB Correct.
12 Correct 657 ms 35452 KB Correct.
13 Correct 731 ms 31012 KB Correct.
14 Execution timed out 3063 ms 93604 KB Time limit exceeded
15 Halted 0 ms 0 KB -