oj.uz

Submission #919613

# Submission time Handle Problem Language Result Execution time Memory
919613 2024-02-01T08:50:09 Z noyancanturk Cyberland (APIO23_cyberland) C++17
100 / 100
 1132 ms 12624 KB 
#pragma GCC optimize("O3,unroll-loops")
#ifndef Local
#include "cyberland.h"
#endif
#include <bits/stdc++.h>
using namespace std;

const int lim=1e5+10;

const double inf=2e18;


using pii=pair<int,int>;
using pdi=pair<double,int>;
vector<pii> v[lim];
 
bool vis[lim];
int n,m,k,h;
void dfs(int node){
    vis[node]=1;
    if(node==h)return;
    for(auto [f,s]:v[node]){
        if(!vis[f]){
            dfs(f);
        }
    }
}

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,k=min(K,100),h=H;
    for(int i=0;i<n;i++){
        vis[i]=0;
        v[i].clear();
    }
    for(int i=0;i<m;i++){
        v[x[i]].push_back({y[i],c[i]});
        v[y[i]].push_back({x[i],c[i]});
    }
    dfs(0);
    double *dist[2];
    dist[0]=new double[n];
    dist[1]=new double[n];
    //for(int i=0;i<n;i++)cerr<<vis[i]<<"\n";
    for(int i=0;i<n;i++){
        dist[0][i]=(arr[i]||!vis[i])?inf:0;
    }
    priority_queue<pdi,vector<pdi>,greater<pdi>>pq;
    for(int i=0;i<n;i++){
        if(!arr[i]&&vis[i]){
            pq.push({0,i});
        }
    }
    dist[0][0]=0;
    pq.push({0,0});
    //else cerr<<arr[0]<<"\n";
    double ans=inf;
    for(int rp=0;rp<min(k+1,100);rp++){
        /*
        for(int i=0;i<n;i++){
            cerr<<dist[0][i]<<" ";
        }cerr<<"\n";
        */
        for(int i=0;i<n;i++){
            dist[1][i]=inf;
        }
        while(pq.size()){
            auto nn=pq.top();
            pq.pop();
            double cost=nn.first;
            int node=nn.second;
            /*
            cerr<<node<<" "<<cost<<" visited\n";
            cerr<<cost<<" "<<dist[0][node]<<"\n";
            */
            if(dist[0][node]<cost||node==h)continue;
            //cerr<<"ok\n";
            for(auto j:v[node]){
                //cerr<<j.first<<" "<<cost+j.second<<"\n";
                //if(j.first==4&&cost+j.second==2)cerr<<node<<"\n";
                if(arr[j.first]&&cost+j.second<dist[0][j.first]){
                    dist[0][j.first]=cost+j.second;
                    pq.push({cost+j.second,j.first});

                    //cerr<<node<<" inserted "<<j.first<<" "<<cost+j.second<<"\n";
                    //cerr<<dist[0][j.first]<<" "<<cost+j.second<<"\n";
                }
                if(arr[j.first]==2&&(cost+j.second)/2<dist[1][j.first]){
                    dist[1][j.first]=min(dist[1][j.first],(cost+j.second)/2);
                }
                //else cerr<<cost<<" "<<j.second<<" "<<dist[0][j.first]<<"\n";
            }
        }
        /*
        for(int i=0;i<n;i++){
            cerr<<dist[0][i]<<" ";
        }cerr<<"\n";
        for(int i=0;i<n;i++){
            cerr<<dist[1][i]<<" ";
        }cerr<<"\n";
        */
        //cerr<<h<<"\n";
        for(int i=0;i<n;i++){
            if(dist[1][i]!=inf)pq.push({dist[1][i],i});
        }
        ans=min(ans,dist[0][h]);
        ans=min(ans,dist[1][h]);
        //cerr<<ans<<"\n";
        swap(dist[0],dist[1]);
    }
    /*
    for(int i=0;i<n;i++){
        cerr<<dist[0][i]<<" ";
    }cerr<<"\n";
    */
    if(ans==inf)return -1;
    return ans;
}

#ifdef Local
int main(){
    freopen(".in","r",stdin);
    freopen(".out","w",stdout);
    int t;
    cin>>t;
    while(t--){
        cin>>n>>m>>k>>h;
        vector<int>x,y,z,arr;
        for(int i=0;i<n;i++){
            int rr;
            cin>>rr;
            arr.push_back(rr);
        }
        for(int i=0;i<m;i++){
            int xx,yy,zz;
            cin>>xx>>yy>>zz;
            x.push_back(xx);
            y.push_back(yy);
            z.push_back(zz);
        }
        cout<<setprecision(30)<<(double)solve(n,m,k,h,x,y,z,arr)<<"\n";
    }
    //cout<<solve(6, 7, 1, 4, {0, 0, 2, 1, 1, 3, 4}, {1, 2, 3, 2, 3, 4, 5}, {2, 3, 4, 2, 5, 3, 2}, {1, 0, 2, 1, 1, 0})<<"\n";
    //cout<<solve(3,3,2,2,{0,1,2},{1,2,0},{2,2,3},{1,2,1})<<"\n";
}
#endif

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 3416 KB Correct.
2 Correct 21 ms 3420 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 3512 KB Correct.
2 Correct 23 ms 3672 KB Correct.
3 Correct 23 ms 3664 KB Correct.
4 Correct 23 ms 3676 KB Correct.
5 Correct 23 ms 3672 KB Correct.
6 Correct 21 ms 3928 KB Correct.
7 Correct 26 ms 4176 KB Correct.
8 Correct 12 ms 4440 KB Correct.
9 Correct 22 ms 3676 KB Correct.
10 Correct 22 ms 3584 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 3676 KB Correct.
2 Correct 23 ms 3676 KB Correct.
3 Correct 22 ms 3664 KB Correct.
4 Correct 27 ms 3672 KB Correct.
5 Correct 24 ms 3672 KB Correct.
6 Correct 6 ms 3672 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 7768 KB Correct.
2 Correct 56 ms 3920 KB Correct.
3 Correct 44 ms 3532 KB Correct.
4 Correct 46 ms 3664 KB Correct.
5 Correct 34 ms 3408 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 3672 KB Correct.
2 Correct 22 ms 3664 KB Correct.
3 Correct 21 ms 3556 KB Correct.
4 Correct 21 ms 4184 KB Correct.
5 Correct 19 ms 3676 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 3672 KB Correct.
2 Correct 20 ms 3672 KB Correct.
3 Correct 37 ms 9296 KB Correct.
4 Correct 15 ms 4184 KB Correct.
5 Correct 22 ms 3672 KB Correct.
6 Correct 22 ms 3664 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 3664 KB Correct.
2 Correct 11 ms 3108 KB Correct.
3 Correct 305 ms 11316 KB Correct.
4 Correct 200 ms 8272 KB Correct.
5 Correct 213 ms 10632 KB Correct.
6 Correct 103 ms 8908 KB Correct.
7 Correct 202 ms 7808 KB Correct.
8 Correct 148 ms 6480 KB Correct.
9 Correct 47 ms 4700 KB Correct.
10 Correct 53 ms 4436 KB Correct.
11 Correct 122 ms 6228 KB Correct.
12 Correct 51 ms 4652 KB Correct.
13 Correct 50 ms 4692 KB Correct.
14 Correct 201 ms 9196 KB Correct.
15 Correct 182 ms 6944 KB Correct.
16 Correct 49 ms 4612 KB Correct.
17 Correct 56 ms 4868 KB Correct.
18 Correct 54 ms 5012 KB Correct.
19 Correct 157 ms 6480 KB Correct.
20 Correct 4 ms 2904 KB Correct.
21 Correct 5 ms 3160 KB Correct.
22 Correct 13 ms 3416 KB Correct.

Subtask #8
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 3664 KB Correct.
2 Correct 21 ms 2904 KB Correct.
3 Correct 265 ms 12624 KB Correct.
4 Correct 243 ms 4776 KB Correct.
5 Correct 592 ms 10708 KB Correct.
6 Correct 270 ms 8908 KB Correct.
7 Correct 500 ms 9508 KB Correct.
8 Correct 170 ms 6428 KB Correct.
9 Correct 82 ms 4432 KB Correct.
10 Correct 82 ms 4432 KB Correct.
11 Correct 123 ms 5716 KB Correct.
12 Correct 94 ms 4688 KB Correct.
13 Correct 89 ms 4692 KB Correct.
14 Correct 1132 ms 10128 KB Correct.
15 Correct 867 ms 9720 KB Correct.
16 Correct 348 ms 7856 KB Correct.
17 Correct 208 ms 6480 KB Correct.
18 Correct 86 ms 4604 KB Correct.
19 Correct 100 ms 4852 KB Correct.
20 Correct 96 ms 4692 KB Correct.
21 Correct 288 ms 6296 KB Correct.
22 Correct 7 ms 2904 KB Correct.
23 Correct 7 ms 2904 KB Correct.
24 Correct 23 ms 3416 KB Correct.