oj.uz

Submission #777213

# Submission time Handle Problem Language Result Execution time Memory
777213 2023-07-08T19:10:18 Z groshi Cyberland (APIO23_cyberland) C++17
97 / 100
 3000 ms 93216 KB 
#include<bits/stdc++.h>
#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:20:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |     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:44:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |     for(int i=0;i<moge.size();i++)
      |                 ~^~~~~~~~~~~~
cyberland.cpp:61:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |         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 33356 KB Correct.
2 Correct 29 ms 33336 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 28280 KB Correct.
2 Correct 43 ms 33880 KB Correct.
3 Correct 35 ms 32212 KB Correct.
4 Correct 37 ms 33396 KB Correct.
5 Correct 38 ms 33488 KB Correct.
6 Correct 30 ms 25548 KB Correct.
7 Correct 48 ms 33852 KB Correct.
8 Correct 23 ms 13284 KB Correct.
9 Correct 36 ms 33888 KB Correct.
10 Correct 35 ms 33348 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 32348 KB Correct.
2 Correct 42 ms 31860 KB Correct.
3 Correct 35 ms 29900 KB Correct.
4 Correct 37 ms 34200 KB Correct.
5 Correct 36 ms 34044 KB Correct.
6 Correct 7 ms 5716 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 169 ms 41148 KB Correct.
2 Correct 209 ms 32636 KB Correct.
3 Correct 176 ms 30176 KB Correct.
4 Correct 190 ms 31156 KB Correct.
5 Correct 165 ms 33432 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 31444 KB Correct.
2 Correct 35 ms 32544 KB Correct.
3 Correct 34 ms 32208 KB Correct.
4 Correct 31 ms 25020 KB Correct.
5 Correct 34 ms 33464 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 32468 KB Correct.
2 Correct 30 ms 28536 KB Correct.
3 Correct 65 ms 49832 KB Correct.
4 Correct 24 ms 23948 KB Correct.
5 Correct 37 ms 34188 KB Correct.
6 Correct 33 ms 29772 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 206 ms 29312 KB Correct.
2 Correct 28 ms 3892 KB Correct.
3 Correct 597 ms 66964 KB Correct.
4 Correct 502 ms 63956 KB Correct.
5 Correct 695 ms 59924 KB Correct.
6 Correct 338 ms 27176 KB Correct.
7 Correct 465 ms 62060 KB Correct.
8 Correct 474 ms 63036 KB Correct.
9 Correct 184 ms 29452 KB Correct.
10 Correct 186 ms 29936 KB Correct.
11 Correct 460 ms 63908 KB Correct.
12 Correct 189 ms 34484 KB Correct.
13 Correct 202 ms 30368 KB Correct.
14 Correct 393 ms 59884 KB Correct.
15 Correct 461 ms 58800 KB Correct.
16 Correct 182 ms 31772 KB Correct.
17 Correct 215 ms 32936 KB Correct.
18 Correct 216 ms 31668 KB Correct.
19 Correct 489 ms 62712 KB Correct.
20 Correct 15 ms 3336 KB Correct.
21 Correct 15 ms 3832 KB Correct.
22 Correct 26 ms 3424 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 696 ms 29340 KB Correct.
2 Correct 85 ms 6008 KB Correct.
3 Correct 546 ms 70100 KB Correct.
4 Correct 1049 ms 61324 KB Correct.
5 Correct 2538 ms 92612 KB Correct.
6 Correct 1377 ms 76492 KB Correct.
7 Correct 1150 ms 54412 KB Correct.
8 Correct 1238 ms 63844 KB Correct.
9 Correct 664 ms 29916 KB Correct.
10 Correct 659 ms 31120 KB Correct.
11 Correct 2511 ms 88192 KB Correct.
12 Correct 663 ms 35004 KB Correct.
13 Correct 738 ms 30792 KB Correct.
14 Execution timed out 3055 ms 93216 KB Time limit exceeded
15 Halted 0 ms 0 KB -