oj.uz

Submission #783577

# Submission time Handle Problem Language Result Execution time Memory
783577 2023-07-15T04:24:28 Z vjudge1 Cyberland (APIO23_cyberland) C++17
97 / 100
 3000 ms 137960 KB 
#include <bits/stdc++.h>
using namespace std;
using pii=pair<int,int>;
constexpr int N=1e5+5,KX=70;
constexpr double INF=1e99;
int n,m,kk,h,ty[N];
vector<pii> g[N];
bool reach[N];
double f[N][KX+3][2];
vector<int> st;
inline void bfsinit(int s){
    queue<int> q;
    memset(reach,0,n*sizeof(bool));
    reach[s]=true,
    q.emplace(s);
    while(!q.empty()){
        int u{q.front()};q.pop();
        for(auto e:g[u]){
            int v{e.first};
            if(!reach[v]){
                reach[v]=true,
                q.emplace(v);
            }
        }
    }
}
inline void dijx(){
    struct Q{
        int u,d;
        double dis;
        bool div2;
        Q(){}
        Q(int u,int d,double ds,bool d2):
            u{u},d{d},dis{ds},div2{d2}{}
        inline bool operator<(const Q &b)const{
            return dis>b.dis;
        }
    };
    queue<Q> q;
    static bool inq[N][KX+3][2];
    for(int i{0};i<n;++i){
        for(int j{0};j<=kk;++j){
            f[i][j][0]=f[i][j][1]=INF;
            inq[i][j][0]=inq[i][j][1]=false;
        }
    }
    for(int s:st){
    	f[s][0][0]=0.0;
        q.emplace(s,0,f[s][0][0],false);
        inq[s][0][0]=true;
    }
    while(!q.empty()){
        auto t=q.front();q.pop();
        inq[t.u][t.d][t.div2]=false;
        double tdis=f[t.u][t.d][t.div2];
        if(t.d<kk&&!t.div2&&ty[t.u]==2&&tdis/2.0<f[t.u][t.d+1][1]){
            f[t.u][t.d+1][1]=tdis/2.0;
            if(!inq[t.u][t.d+1][1]){
                q.emplace(t.u,t.d+1,f[t.u][t.d+1][1],true);
                inq[t.u][t.d+1][1]=true;
            }
        }
        for(pii e:g[t.u]){
            int v{e.first},w{e.second};
            if(tdis+w<f[v][t.d][0]){
                f[v][t.d][0]=tdis+w;
                if(!inq[v][t.d][0]){
                    q.emplace(v,t.d,f[v][t.d][0],false);
                    inq[v][t.d][0]=true;
                }
            }
        }
    }
}
double solve(int N, int M, int K, int H, std::vector<int> x, std::vector<int> y, std::vector<int> c, std::vector<int> arr){
    n=N,m=M,kk=K,h=H;
    kk=min(kk,KX);
    for(int i{0};i<n;++i){
        ty[i]=arr[i];
        g[i].clear();
    }
    for(int i{0};i<m;++i){
        int u{x[i]},v{y[i]},w{c[i]};
        if(u!=h) g[u].emplace_back(v,w);
        if(v!=h) g[v].emplace_back(u,w);
    }
    bfsinit(0);
    if(!reach[h]) return -1;
    for(int i{0};i<n;++i){
        if(i==0||(ty[i]==0&&reach[i])){
            st.emplace_back(i);
        }
    }
    dijx();
    double ans{INF};
    for(int i{0};i<=kk;++i){
        ans=min({ans,f[h][i][0],f[h][i][1]});
    }
    st.clear();
    return ans;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 2772 KB Correct.
2 Correct 17 ms 2768 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 4080 KB Correct.
2 Correct 23 ms 4052 KB Correct.
3 Correct 24 ms 4052 KB Correct.
4 Correct 22 ms 4080 KB Correct.
5 Correct 23 ms 4100 KB Correct.
6 Correct 24 ms 15964 KB Correct.
7 Correct 29 ms 15688 KB Correct.
8 Correct 21 ms 29244 KB Correct.
9 Correct 21 ms 2772 KB Correct.
10 Correct 21 ms 2864 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 3960 KB Correct.
2 Correct 22 ms 4052 KB Correct.
3 Correct 21 ms 4124 KB Correct.
4 Correct 23 ms 2860 KB Correct.
5 Correct 23 ms 2772 KB Correct.
6 Correct 13 ms 13648 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 82948 KB Correct.
2 Correct 148 ms 4148 KB Correct.
3 Correct 138 ms 4172 KB Correct.
4 Correct 146 ms 4256 KB Correct.
5 Correct 111 ms 2860 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 4152 KB Correct.
2 Correct 23 ms 4092 KB Correct.
3 Correct 20 ms 4092 KB Correct.
4 Correct 25 ms 15932 KB Correct.
5 Correct 18 ms 2832 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 4156 KB Correct.
2 Correct 17 ms 4028 KB Correct.
3 Correct 31 ms 8132 KB Correct.
4 Correct 16 ms 10816 KB Correct.
5 Correct 22 ms 2864 KB Correct.
6 Correct 19 ms 4148 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 153 ms 4064 KB Correct.
2 Correct 24 ms 4052 KB Correct.
3 Correct 415 ms 133360 KB Correct.
4 Correct 144 ms 32292 KB Correct.
5 Correct 955 ms 57036 KB Correct.
6 Correct 465 ms 21364 KB Correct.
7 Correct 138 ms 35140 KB Correct.
8 Correct 118 ms 7476 KB Correct.
9 Correct 127 ms 4232 KB Correct.
10 Correct 116 ms 4096 KB Correct.
11 Correct 130 ms 4544 KB Correct.
12 Correct 142 ms 4128 KB Correct.
13 Correct 147 ms 4336 KB Correct.
14 Correct 186 ms 66008 KB Correct.
15 Correct 156 ms 19632 KB Correct.
16 Correct 127 ms 4192 KB Correct.
17 Correct 165 ms 4160 KB Correct.
18 Correct 143 ms 4160 KB Correct.
19 Correct 422 ms 4160 KB Correct.
20 Correct 10 ms 2944 KB Correct.
21 Correct 12 ms 3408 KB Correct.
22 Correct 19 ms 4328 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 504 ms 4168 KB Correct.
2 Correct 73 ms 4180 KB Correct.
3 Correct 208 ms 137960 KB Correct.
4 Correct 228 ms 11380 KB Correct.
5 Execution timed out 3060 ms 60840 KB Time limit exceeded
6 Halted 0 ms 0 KB -