oj.uz

Submission #777509

# Submission time Handle Problem Language Result Execution time Memory
777509 2023-07-09T09:54:39 Z groshi Cyberland (APIO23_cyberland) C++17
100 / 100
 1368 ms 87588 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;
struct node {
    double di;
    int u, k;
    bool operator < (const node& o) const {
        if (k != o.k) return k > o.k;
        return di > o.di;
    }
};
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++)
    {
        if(x[i]!=h)
            w[x[i]].Q.push_back(y[i]),w[x[i]].Q.push_back(c[i]);
        if(y[i]!=h)
            w[y[i]].Q.push_back(x[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<node> 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 [ile,x,typ]=kolejka.top();
        kolejka.pop();
        if(ile!=w[x].dp[typ])
            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 || typ+1>k)
                continue;
            dodaj+=ile;
            dodaj/=2.0;
            if(w[pom].dp[typ+1]>dodaj)
                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:28:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |     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:52:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |     for(int i=0;i<moge.size();i++)
      |                 ~^~~~~~~~~~~~
cyberland.cpp:64:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |         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 29 ms 33168 KB Correct.
2 Correct 40 ms 33100 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 28196 KB Correct.
2 Correct 38 ms 33844 KB Correct.
3 Correct 35 ms 32184 KB Correct.
4 Correct 37 ms 33352 KB Correct.
5 Correct 35 ms 33492 KB Correct.
6 Correct 29 ms 25580 KB Correct.
7 Correct 39 ms 33876 KB Correct.
8 Correct 17 ms 13156 KB Correct.
9 Correct 35 ms 33924 KB Correct.
10 Correct 34 ms 33308 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 32384 KB Correct.
2 Correct 48 ms 31820 KB Correct.
3 Correct 43 ms 29908 KB Correct.
4 Correct 36 ms 34132 KB Correct.
5 Correct 37 ms 33992 KB Correct.
6 Correct 7 ms 5716 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 39120 KB Correct.
2 Correct 98 ms 32584 KB Correct.
3 Correct 81 ms 30060 KB Correct.
4 Correct 90 ms 31116 KB Correct.
5 Correct 58 ms 33352 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 31396 KB Correct.
2 Correct 34 ms 32528 KB Correct.
3 Correct 34 ms 32180 KB Correct.
4 Correct 32 ms 24900 KB Correct.
5 Correct 33 ms 33440 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 32508 KB Correct.
2 Correct 29 ms 28576 KB Correct.
3 Correct 65 ms 49772 KB Correct.
4 Correct 23 ms 23884 KB Correct.
5 Correct 34 ms 34116 KB Correct.
6 Correct 31 ms 29812 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 101 ms 29144 KB Correct.
2 Correct 14 ms 3028 KB Correct.
3 Correct 703 ms 64956 KB Correct.
4 Correct 274 ms 63196 KB Correct.
5 Correct 364 ms 27972 KB Correct.
6 Correct 144 ms 11256 KB Correct.
7 Correct 272 ms 62008 KB Correct.
8 Correct 225 ms 62968 KB Correct.
9 Correct 86 ms 29448 KB Correct.
10 Correct 92 ms 30040 KB Correct.
11 Correct 195 ms 63944 KB Correct.
12 Correct 99 ms 34544 KB Correct.
13 Correct 105 ms 30684 KB Correct.
14 Correct 269 ms 58020 KB Correct.
15 Correct 257 ms 58560 KB Correct.
16 Correct 87 ms 31540 KB Correct.
17 Correct 99 ms 32792 KB Correct.
18 Correct 96 ms 31752 KB Correct.
19 Correct 231 ms 62612 KB Correct.
20 Correct 6 ms 3284 KB Correct.
21 Correct 7 ms 3564 KB Correct.
22 Correct 13 ms 1364 KB Correct.

Subtask #8
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 190 ms 29108 KB Correct.
2 Correct 27 ms 2952 KB Correct.
3 Correct 918 ms 69972 KB Correct.
4 Correct 302 ms 61056 KB Correct.
5 Correct 751 ms 27916 KB Correct.
6 Correct 290 ms 11332 KB Correct.
7 Correct 487 ms 53696 KB Correct.
8 Correct 277 ms 63816 KB Correct.
9 Correct 167 ms 29476 KB Correct.
10 Correct 152 ms 29992 KB Correct.
11 Correct 140 ms 87588 KB Correct.
12 Correct 172 ms 34556 KB Correct.
13 Correct 165 ms 30540 KB Correct.
14 Correct 1368 ms 38448 KB Correct.
15 Correct 1300 ms 62932 KB Correct.
16 Correct 442 ms 60056 KB Correct.
17 Correct 300 ms 62928 KB Correct.
18 Correct 159 ms 32028 KB Correct.
19 Correct 182 ms 33168 KB Correct.
20 Correct 177 ms 32072 KB Correct.
21 Correct 445 ms 62524 KB Correct.
22 Correct 12 ms 3412 KB Correct.
23 Correct 13 ms 3592 KB Correct.
24 Correct 24 ms 1364 KB Correct.