oj.uz

Submission #751809

# Submission time Handle Problem Language Result Execution time Memory
751809 2023-06-01T13:46:33 Z 1075508020060209tc Cyberland (APIO23_cyberland) C++17
44 / 100
 177 ms 42020 KB 
#include "cyberland.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long



int n;int m;int KK;int HH;
ll ar[200005];
ll xar[200005];ll yar[200005];ll car[200005];
vector<pair<int,ll>>e[200005];


void inp(){
  //  cin>>n>>m>>KK>>HH;
    HH++;
    for(int i=1;i<=n;i++){
      //  cin>>ar[i];
        e[i].clear();
    }
    for(int i=1;i<=m;i++){
        //cin>>xar[i]>>yar[i]>>car[i];
        xar[i]++;yar[i]++;
        e[xar[i]].push_back({yar[i],car[i]});
        e[yar[i]].push_back({xar[i],car[i]});
    }
}

int uf[200005];
int fin(int x){
if(uf[x]==x){return x;}
uf[x]=fin(uf[x]);
return uf[x];
}
void mrg(int a,int b){
int pa=fin(a);int pb=fin(b);
if(pa==pb){return;}
uf[pa]=pb;
}

double dis[110][100005];
int vis[110][100005];

double slv(){
for(int i=1;i<=n;i++){
    uf[i]=i;
}
for(int i=1;i<=m;i++){
    if(xar[i]==HH||yar[i]==HH){continue;}
    mrg(xar[i],yar[i]);
}
/*
*/
priority_queue<pair<double,pair<int,int>>,vector<pair<double,pair<int,int>>>,greater<pair<double,pair<int,int>>>>pq;
KK=min(KK,70);
for(int k=0;k<=KK;k++){
    for(int i=1;i<=n;i++){
        dis[k][i]=1e16;
        vis[k][i]=0;
    }
}
dis[0][1]=0;
pq.push({0,{0,1}});
for(int i=2;i<=n;i++){
    if(ar[i]==0&&fin(i)==fin(1)){
        pq.push({0,{0,i}});
        dis[0][i]=0;
    }
}

for(int i=1;i<=m;i++){
    mrg(xar[i],yar[i]);
}
if(fin(1)!=fin(HH)){
    return -1;
}

while(pq.size()){
    int nw=pq.top().second.second;
    int nwk=pq.top().second.first;
    pq.pop();
    if(vis[nwk][nw]){continue;}
    vis[nwk][nw]=1;
    if(nw==HH){continue;}
    for(int i=0;i<e[nw].size();i++){
        int v=e[nw][i].first;
        ll w=e[nw][i].second;
        if(vis[nwk][v]){continue;}
        if(dis[nwk][v]>dis[nwk][nw]+w){
            dis[nwk][v]=dis[nwk][nw]+w;
            pq.push({dis[nwk][v],{nwk,v}});
        }
    }
}

for(int k=1;k<=KK;k++){
    for(int i=1;i<=n;i++){
        if(vis[k-1][i]&&ar[i]==2){
            dis[k][i]=dis[k-1][i]/2.;
            pq.push({dis[k][i],{k,i}});
        }
    }
    while(pq.size()){
        int nw=pq.top().second.second;
        int nwk=pq.top().second.first;
        pq.pop();
        if(vis[nwk][nw]){continue;}
        vis[nwk][nw]=1;
        if(nw==HH){continue;}
        for(int i=0;i<e[nw].size();i++){
            int v=e[nw][i].first;
            double w=e[nw][i].second;
            if(vis[nwk][v]){continue;}
            if(dis[nwk][v]>dis[nwk][nw]+w){
                dis[nwk][v]=dis[nwk][nw]+w;
                pq.push({dis[nwk][v],{nwk,v}});
            }
        }
    }
}



double ans=dis[0][HH];

for(int i=1;i<=KK;i++){
    if(!vis[i][HH]){continue;}
    ans=min(ans,dis[i][HH]);
}
/*
for(int i=0;i<=3;i++){
    for(int j=1;j<=n;j++){
        cout<<dis[i][j]<<" ";
    }cout<<endl;
}
*/
return ans;
}
//#define int int
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){
/*    cin>>N>>M>>K>>H;

    for(int i=1;i<=N;i++){
        int v;
        cin>>v;
        arr.push_back(v);
    }
  //  cout<<M<<" ";
    for(int i=1;i<=M;i++){
        int a;int b;int cc;
        cin>>a>>b>>cc;
        x.push_back(a);y.push_back(b);c.push_back(cc);
      //  cout<<i<<" "<<M<<endl;
    }
*/



    n=N;m=M;KK=K;HH=H;
    for(int i=0;i<x.size();i++){
        xar[i+1]=x[i];
        yar[i+1]=y[i];
        car[i+1]=c[i];
    }
    for(int i=0;i<arr.size();i++){
        ar[i+1]=arr[i];
    }
   // cout<<"hehe";
    inp();
    return slv();
}

/*
signed main()
{

    cout<<fixed<<setprecision(7)<<solve(0,0,0,0,{},{},{},{});

 //   inp();
   // cout<<slv();






    return 0;
}



*/

Compilation message

cyberland.cpp: In function 'double slv()':
cyberland.cpp:85:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |     for(int i=0;i<e[nw].size();i++){
      |                 ~^~~~~~~~~~~~~
cyberland.cpp:110:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  110 |         for(int i=0;i<e[nw].size();i++){
      |                     ~^~~~~~~~~~~~~
cyberland.cpp: In function 'double solve(int, int, int, int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
cyberland.cpp:160:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  160 |     for(int i=0;i<x.size();i++){
      |                 ~^~~~~~~~~
cyberland.cpp:165:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  165 |     for(int i=0;i<arr.size();i++){
      |                 ~^~~~~~~~~~~

Subtask #1
0.0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 24 ms 5452 KB Wrong Answer.
2 Halted 0 ms 0 KB -

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 5932 KB Correct.
2 Correct 35 ms 5972 KB Correct.
3 Correct 29 ms 5912 KB Correct.
4 Correct 30 ms 5904 KB Correct.
5 Correct 29 ms 5972 KB Correct.
6 Correct 26 ms 10196 KB Correct.
7 Correct 32 ms 9984 KB Correct.
8 Correct 18 ms 14796 KB Correct.
9 Correct 27 ms 5480 KB Correct.
10 Correct 26 ms 5460 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 5844 KB Correct.
2 Correct 28 ms 5904 KB Correct.
3 Correct 27 ms 5936 KB Correct.
4 Correct 28 ms 5460 KB Correct.
5 Correct 28 ms 5468 KB Correct.
6 Correct 9 ms 9324 KB Correct.

Subtask #4
0.0 / 19.0

# Verdict Execution time Memory Grader output
1 Incorrect 118 ms 33928 KB Wrong Answer.
2 Halted 0 ms 0 KB -

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 6008 KB Correct.
2 Correct 28 ms 6032 KB Correct.
3 Correct 26 ms 5972 KB Correct.
4 Correct 29 ms 10528 KB Correct.
5 Correct 26 ms 5460 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 5964 KB Correct.
2 Correct 27 ms 6044 KB Correct.
3 Correct 59 ms 42020 KB Correct.
4 Correct 19 ms 9172 KB Correct.
5 Correct 27 ms 5464 KB Correct.
6 Correct 27 ms 5972 KB Correct.

Subtask #7
0.0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 98 ms 6008 KB Wrong Answer.
2 Halted 0 ms 0 KB -

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Incorrect 177 ms 6892 KB Wrong Answer.
2 Halted 0 ms 0 KB -