oj.uz

답안 #751820

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
751820 2023-06-01T14:17:45 Z 1075508020060209tc 사이버랜드 (APIO23_cyberland) C++17
100 / 100
 1189 ms 101076 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){
            double vl=1e16;
            for(int j=0;j<e[i].size();j++){
                int v=e[i][j].first;
                double w=e[i][j].second;
                if(v==HH){continue;}
                vl=min(vl,dis[k-1][v]+w);
            }
            dis[k][i]=vl/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:100:26: 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]
  100 |             for(int j=0;j<e[i].size();j++){
      |                         ~^~~~~~~~~~~~
cyberland.cpp:117: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]
  117 |         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:167:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  167 |     for(int i=0;i<x.size();i++){
      |                 ~^~~~~~~~~
cyberland.cpp:172:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  172 |     for(int i=0;i<arr.size();i++){
      |                 ~^~~~~~~~~~~

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 24 ms 5500 KB Correct.
2 Correct 24 ms 5460 KB Correct.

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 24 ms 5952 KB Correct.
2 Correct 29 ms 5844 KB Correct.
3 Correct 26 ms 5864 KB Correct.
4 Correct 29 ms 5912 KB Correct.
5 Correct 35 ms 6028 KB Correct.
6 Correct 29 ms 10192 KB Correct.
7 Correct 33 ms 10060 KB Correct.
8 Correct 18 ms 14792 KB Correct.
9 Correct 28 ms 5460 KB Correct.
10 Correct 27 ms 5472 KB Correct.

Subtask #3
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 28 ms 5932 KB Correct.
2 Correct 28 ms 5940 KB Correct.
3 Correct 29 ms 5948 KB Correct.
4 Correct 29 ms 5472 KB Correct.
5 Correct 29 ms 5460 KB Correct.
6 Correct 9 ms 9428 KB Correct.

Subtask #4
19.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 117 ms 33840 KB Correct.
2 Correct 103 ms 5876 KB Correct.
3 Correct 92 ms 5896 KB Correct.
4 Correct 112 ms 5968 KB Correct.
5 Correct 68 ms 5456 KB Correct.

Subtask #5
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 24 ms 5996 KB Correct.
2 Correct 29 ms 5972 KB Correct.
3 Correct 26 ms 6024 KB Correct.
4 Correct 30 ms 10524 KB Correct.
5 Correct 24 ms 5476 KB Correct.

Subtask #6
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 27 ms 6040 KB Correct.
2 Correct 23 ms 6032 KB Correct.
3 Correct 60 ms 42080 KB Correct.
4 Correct 22 ms 9244 KB Correct.
5 Correct 28 ms 5484 KB Correct.
6 Correct 25 ms 5972 KB Correct.

Subtask #7
29.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 109 ms 5960 KB Correct.
2 Correct 21 ms 6356 KB Correct.
3 Correct 491 ms 36784 KB Correct.
4 Correct 264 ms 14100 KB Correct.
5 Correct 434 ms 27460 KB Correct.
6 Correct 187 ms 16972 KB Correct.
7 Correct 272 ms 14252 KB Correct.
8 Correct 204 ms 7048 KB Correct.
9 Correct 90 ms 5972 KB Correct.
10 Correct 83 ms 5964 KB Correct.
11 Correct 190 ms 6500 KB Correct.
12 Correct 102 ms 5964 KB Correct.
13 Correct 103 ms 6040 KB Correct.
14 Correct 265 ms 18128 KB Correct.
15 Correct 229 ms 9552 KB Correct.
16 Correct 95 ms 5992 KB Correct.
17 Correct 110 ms 5992 KB Correct.
18 Correct 99 ms 6020 KB Correct.
19 Correct 258 ms 5972 KB Correct.
20 Correct 8 ms 5460 KB Correct.
21 Correct 9 ms 5844 KB Correct.
22 Correct 17 ms 6612 KB Correct.

Subtask #8
3.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 199 ms 6876 KB Correct.
2 Correct 38 ms 7460 KB Correct.
3 Correct 276 ms 101076 KB Correct.
4 Correct 288 ms 10508 KB Correct.
5 Correct 1002 ms 44488 KB Correct.
6 Correct 401 ms 22312 KB Correct.
7 Correct 510 ms 27104 KB Correct.
8 Correct 259 ms 7244 KB Correct.
9 Correct 170 ms 6860 KB Correct.
10 Correct 144 ms 6916 KB Correct.
11 Correct 158 ms 5952 KB Correct.
12 Correct 195 ms 6904 KB Correct.
13 Correct 183 ms 6896 KB Correct.
14 Correct 1189 ms 45124 KB Correct.
15 Correct 915 ms 52940 KB Correct.
16 Correct 437 ms 22168 KB Correct.
17 Correct 287 ms 9328 KB Correct.
18 Correct 164 ms 6852 KB Correct.
19 Correct 218 ms 6916 KB Correct.
20 Correct 189 ms 6940 KB Correct.
21 Correct 514 ms 6820 KB Correct.
22 Correct 12 ms 5844 KB Correct.
23 Correct 15 ms 6660 KB Correct.
24 Correct 33 ms 7420 KB Correct.