oj.uz

Submission #981919

# Submission time Handle Problem Language Result Execution time Memory
981919 2024-05-13T16:28:38 Z 8pete8 Cyberland (APIO23_cyberland) C++17
97 / 100
 3000 ms 93600 KB 
#include "cyberland.h"
#include<iostream>
#include<vector>
#include<queue>
using namespace std;
#define ll long long
#define pb push_back
#define pii pair<int,int>
#define s second
#define f first
using namespace std;
//#define int long long
//#define double long double
const ll inf=1e18,mxn=1e5;
double pre=1e-7;
struct info{
    double cost;
    int cur,use;
    bool operator<(info a)const{return (cost>a.cost);};
};
vector<int>p(mxn+10);
priority_queue<info>pq;
int cur,use;
double cost,ans;
int find(int u){return (p[u]==u)?u:p[u]=find(p[u]);}
double solve(int n,int m,int k,int H,vector<int>x,vector<int>y,vector<int>c,vector<int> arr){
    k=min(k,69);
    for(int i=0;i<n;i++)p[i]=i;
    vector<vector<double>>what(n+1,vector<double>(k+1,inf));
    vector<vector<pii>>adj(n+1);
    for(int i=0;i<m;i++){
        adj[x[i]].pb({y[i],c[i]});
        adj[y[i]].pb({x[i],c[i]});
        p[find(x[i])]=find(y[i]);
    }
    adj[H].clear();
    for(int i=0;i<n;i++)if(arr[i]==0&&find(0)==find(i))pq.push({0,i,0});
    what[0][0]=0;
    pq.push({0,0,0});
    ans=inf;
    while(!pq.empty()){
        cur=pq.top().cur,use=pq.top().use,cost=pq.top().cost;
        pq.pop();
        if(what[cur][use]<cost)continue;
        if(cur==H)ans=min(ans,cost);
        for(auto i:adj[cur]){
            if(what[cur][use]+i.s<what[i.f][use]){
                what[i.f][use]=cost+i.s;
                if(arr[i.f]==0)what[i.f][use]=0;
                pq.push((info){what[i.f][use]*1.0,i.f,use});
            }
            if(arr[cur]==2&&use<k){
                if(what[i.f][use+1]>(cost*1.0)/2+i.s){
                    what[i.f][use+1]=(cost*1.0)/2+i.s;
                    pq.push((info){what[i.f][use+1],i.f,use+1});
                }
            }
        }
    }
    for(int i=0;i<n;i++)adj[i].clear();
    if(ans==inf)return -1;
    return ans;
}
#undef int
/*
int32_t main(){
    int t;cin>>t;
    int n,m,k,h;cin>>n>>m>>k>>h;
    vector<int>x(m),y(m),z(m),arr(n);
    for(int i=0;i<n;i++)cin>>arr[i];
    for(int i=0;i<m;i++)cin>>x[i]>>y[i]>>z[i];
    cout<<solve(n,m,k,h,x,y,z,arr);
}*/
/*
1
4 4 30
3
1 1 2 1
0 1 5
0 2 4
1 3 2
2 3 4
*/

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 860 KB Correct.
2 Correct 17 ms 912 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 1116 KB Correct.
2 Correct 24 ms 1116 KB Correct.
3 Correct 25 ms 1116 KB Correct.
4 Correct 24 ms 1116 KB Correct.
5 Correct 24 ms 1116 KB Correct.
6 Correct 20 ms 4252 KB Correct.
7 Correct 26 ms 4256 KB Correct.
8 Correct 13 ms 8028 KB Correct.
9 Correct 23 ms 956 KB Correct.
10 Correct 22 ms 860 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 1116 KB Correct.
2 Correct 26 ms 1112 KB Correct.
3 Correct 24 ms 1112 KB Correct.
4 Correct 26 ms 860 KB Correct.
5 Correct 25 ms 856 KB Correct.
6 Correct 6 ms 3932 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 244 ms 22988 KB Correct.
2 Correct 382 ms 1220 KB Correct.
3 Correct 324 ms 1240 KB Correct.
4 Correct 343 ms 1224 KB Correct.
5 Correct 243 ms 964 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 1112 KB Correct.
2 Correct 24 ms 1116 KB Correct.
3 Correct 23 ms 1212 KB Correct.
4 Correct 22 ms 4188 KB Correct.
5 Correct 22 ms 960 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 1368 KB Correct.
2 Correct 22 ms 1116 KB Correct.
3 Correct 55 ms 28496 KB Correct.
4 Correct 16 ms 3000 KB Correct.
5 Correct 25 ms 860 KB Correct.
6 Correct 28 ms 1240 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 243 ms 1568 KB Correct.
2 Correct 29 ms 1748 KB Correct.
3 Correct 1381 ms 27500 KB Correct.
4 Correct 1040 ms 7468 KB Correct.
5 Correct 843 ms 50764 KB Correct.
6 Correct 293 ms 25012 KB Correct.
7 Correct 1040 ms 7616 KB Correct.
8 Correct 868 ms 2048 KB Correct.
9 Correct 212 ms 1724 KB Correct.
10 Correct 219 ms 1480 KB Correct.
11 Correct 819 ms 1472 KB Correct.
12 Correct 229 ms 1508 KB Correct.
13 Correct 226 ms 1484 KB Correct.
14 Correct 781 ms 9360 KB Correct.
15 Correct 1080 ms 3144 KB Correct.
16 Correct 213 ms 1488 KB Correct.
17 Correct 285 ms 1588 KB Correct.
18 Correct 254 ms 1660 KB Correct.
19 Correct 776 ms 1752 KB Correct.
20 Correct 16 ms 860 KB Correct.
21 Correct 20 ms 1372 KB Correct.
22 Correct 20 ms 2512 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 731 ms 2312 KB Correct.
2 Correct 82 ms 2904 KB Correct.
3 Correct 435 ms 67924 KB Correct.
4 Correct 2525 ms 4100 KB Correct.
5 Correct 2789 ms 93600 KB Correct.
6 Correct 962 ms 44720 KB Correct.
7 Execution timed out 3074 ms 22396 KB Time limit exceeded
8 Halted 0 ms 0 KB -