oj.uz

Submission #806428

# Submission time Handle Problem Language Result Execution time Memory
806428 2023-08-04T06:42:25 Z irmuun Cyberland (APIO23_cyberland) C++17
97 / 100
 68 ms 59088 KB 
#include<bits/stdc++.h>
#include "cyberland.h"
 
using namespace std;
 
#define ll long long
#define pb push_back
#define ff first
#define ss second
#define all(s) s.begin(),s.end()
#define rall(s) s.rbegin(),s.rend()
 
const double inf=1e18;
 
struct dsu{
    vector<ll>p,sz;
    void init(ll n){
        p.resize(n);
        iota(p.begin(),p.end(),0);
        sz.resize(n);
        fill(sz.begin(),sz.end(),1);
    }
    ll find(ll x){
        if(p[x]==x){
            return x;
        }
        return p[x]=find(p[x]);
    }
    bool same(ll x,ll y){
        x=find(x);
        y=find(y);
        if(x==y){
            return true;
        }
        else{
            return false;
        }
    }
    void merge(ll x,ll y){
        x=find(x);
        y=find(y);
        if(x!=y){
            if(sz[x]<sz[y]){
                swap(x,y);
            }
            sz[x]+=sz[y];
            p[y]=x;
        }
    }
}ds;
 
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,60);
    vector<double>pw(K+1);
    ds.init(N);
    vector<pair<int,int>>adj[N];
    for(int i=0;i<M;i++){
        if(x[i]!=H&&y[i]!=H){
            ds.merge(x[i],y[i]);
        }
        adj[x[i]].pb({c[i],y[i]});
        adj[y[i]].pb({c[i],x[i]});
    }
    pw[0]=1;
    for(int i=1;i<=K;i++){
        pw[i]=pw[i-1]/2;
    }
    arr[0]=0;
    vector<vector<double>>dist(K+1,vector<double>(N,inf));
    using node=tuple<double,int,int>;
    priority_queue<node,vector<node>,greater<node>>pq;
    auto ck=[&](int k,int x,double d){
        if(dist[k][x]>d){
            dist[k][x]=d;
            pq.push({d,k,x});
        }
    };
    ck(K,H,0);
    while(!pq.empty()){
        auto [d,k,x]=pq.top();
        pq.pop();
        if(dist[k][x]<d){
            continue;
        }
        if(arr[x]==0){
            return d;
        }
        for(auto [c,y]:adj[x]){
            if(!ds.same(y,0)){
                continue;
            }
            ck(k,y,d+c*pw[K-k]);
            if(arr[x]==2&&k>0){
                ck(k-1,y,d+c*pw[K-k+1]);
            }
        }
    }
    return -1;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 468 KB Correct.
2 Correct 22 ms 468 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 724 KB Correct.
2 Correct 21 ms 736 KB Correct.
3 Correct 21 ms 724 KB Correct.
4 Correct 21 ms 696 KB Correct.
5 Correct 21 ms 752 KB Correct.
6 Correct 22 ms 3804 KB Correct.
7 Correct 22 ms 3720 KB Correct.
8 Correct 10 ms 7388 KB Correct.
9 Correct 20 ms 488 KB Correct.
10 Correct 20 ms 488 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 732 KB Correct.
2 Correct 19 ms 692 KB Correct.
3 Correct 18 ms 748 KB Correct.
4 Correct 20 ms 484 KB Correct.
5 Correct 20 ms 480 KB Correct.
6 Correct 5 ms 3156 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 20796 KB Correct.
2 Correct 21 ms 724 KB Correct.
3 Correct 20 ms 796 KB Correct.
4 Correct 19 ms 692 KB Correct.
5 Correct 23 ms 504 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 728 KB Correct.
2 Correct 24 ms 696 KB Correct.
3 Correct 25 ms 720 KB Correct.
4 Correct 22 ms 3600 KB Correct.
5 Correct 21 ms 492 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 692 KB Correct.
2 Correct 23 ms 700 KB Correct.
3 Correct 44 ms 27380 KB Correct.
4 Correct 15 ms 2512 KB Correct.
5 Correct 22 ms 480 KB Correct.
6 Correct 20 ms 720 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 668 KB Correct.
2 Correct 3 ms 852 KB Correct.
3 Correct 49 ms 24612 KB Correct.
4 Correct 39 ms 6460 KB Correct.
5 Correct 41 ms 15180 KB Correct.
6 Correct 24 ms 7116 KB Correct.
7 Correct 55 ms 6568 KB Correct.
8 Correct 39 ms 1372 KB Correct.
9 Correct 24 ms 696 KB Correct.
10 Correct 29 ms 668 KB Correct.
11 Correct 40 ms 780 KB Correct.
12 Correct 21 ms 760 KB Correct.
13 Correct 21 ms 720 KB Correct.
14 Correct 39 ms 8188 KB Correct.
15 Correct 38 ms 2468 KB Correct.
16 Correct 21 ms 740 KB Correct.
17 Correct 22 ms 812 KB Correct.
18 Correct 21 ms 740 KB Correct.
19 Correct 44 ms 712 KB Correct.
20 Correct 2 ms 340 KB Correct.
21 Correct 2 ms 520 KB Correct.
22 Correct 3 ms 980 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 964 KB Correct.
2 Correct 3 ms 1236 KB Correct.
3 Incorrect 68 ms 59088 KB Wrong Answer.
4 Halted 0 ms 0 KB -