oj.uz

Submission #783574

# Submission time Handle Problem Language Result Execution time Memory
783574 2023-07-15T04:22:38 Z vjudge1 Cyberland (APIO23_cyberland) C++17
97 / 100
 3000 ms 135180 KB 
#include <bits/stdc++.h>
using namespace std;
using pii=pair<int,int>;
constexpr int N=1e5+5,KX=67;
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 2912 KB Correct.
2 Correct 18 ms 3112 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 4348 KB Correct.
2 Correct 21 ms 4964 KB Correct.
3 Correct 21 ms 4892 KB Correct.
4 Correct 21 ms 4892 KB Correct.
5 Correct 23 ms 4940 KB Correct.
6 Correct 22 ms 16244 KB Correct.
7 Correct 29 ms 16136 KB Correct.
8 Correct 20 ms 28668 KB Correct.
9 Correct 21 ms 3540 KB Correct.
10 Correct 20 ms 3628 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 4908 KB Correct.
2 Correct 21 ms 4788 KB Correct.
3 Correct 20 ms 4924 KB Correct.
4 Correct 24 ms 3160 KB Correct.
5 Correct 21 ms 3668 KB Correct.
6 Correct 9 ms 13464 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 119 ms 80896 KB Correct.
2 Correct 139 ms 4900 KB Correct.
3 Correct 125 ms 5000 KB Correct.
4 Correct 135 ms 5008 KB Correct.
5 Correct 104 ms 3580 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 4948 KB Correct.
2 Correct 19 ms 4856 KB Correct.
3 Correct 19 ms 4860 KB Correct.
4 Correct 24 ms 16332 KB Correct.
5 Correct 17 ms 3556 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 4940 KB Correct.
2 Correct 19 ms 4916 KB Correct.
3 Correct 40 ms 9548 KB Correct.
4 Correct 16 ms 11008 KB Correct.
5 Correct 20 ms 3712 KB Correct.
6 Correct 19 ms 4604 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 170 ms 4964 KB Correct.
2 Correct 24 ms 4084 KB Correct.
3 Correct 383 ms 130392 KB Correct.
4 Correct 133 ms 33348 KB Correct.
5 Correct 901 ms 56936 KB Correct.
6 Correct 391 ms 22092 KB Correct.
7 Correct 133 ms 35856 KB Correct.
8 Correct 114 ms 9028 KB Correct.
9 Correct 121 ms 5048 KB Correct.
10 Correct 115 ms 4940 KB Correct.
11 Correct 129 ms 6240 KB Correct.
12 Correct 141 ms 4816 KB Correct.
13 Correct 143 ms 4976 KB Correct.
14 Correct 166 ms 65004 KB Correct.
15 Correct 152 ms 21068 KB Correct.
16 Correct 136 ms 4940 KB Correct.
17 Correct 161 ms 5196 KB Correct.
18 Correct 144 ms 5200 KB Correct.
19 Correct 395 ms 5988 KB Correct.
20 Correct 10 ms 2808 KB Correct.
21 Correct 10 ms 3348 KB Correct.
22 Correct 19 ms 4428 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 476 ms 4720 KB Correct.
2 Correct 67 ms 4252 KB Correct.
3 Correct 231 ms 135180 KB Correct.
4 Correct 209 ms 13212 KB Correct.
5 Execution timed out 3071 ms 60712 KB Time limit exceeded
6 Halted 0 ms 0 KB -