oj.uz

Submission #806364

# Submission time Handle Problem Language Result Execution time Memory
806364 2023-08-04T06:16:44 Z irmuun Cyberland (APIO23_cyberland) C++17
44 / 100
 41 ms 29156 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[y]==2&&k>0){
                ck(k-1,y,d+c*pw[K-k+1]);
            }
        }
    }
    return -1;
}

Subtask #1
0.0 / 5.0

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

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 1592 KB Correct.
2 Correct 21 ms 1760 KB Correct.
3 Correct 20 ms 1740 KB Correct.
4 Correct 21 ms 1688 KB Correct.
5 Correct 26 ms 1732 KB Correct.
6 Correct 21 ms 4676 KB Correct.
7 Correct 23 ms 4472 KB Correct.
8 Correct 10 ms 7836 KB Correct.
9 Correct 21 ms 1364 KB Correct.
10 Correct 20 ms 1372 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 1704 KB Correct.
2 Correct 20 ms 1644 KB Correct.
3 Correct 23 ms 1656 KB Correct.
4 Correct 21 ms 1340 KB Correct.
5 Correct 20 ms 1372 KB Correct.
6 Correct 4 ms 3264 KB Correct.

Subtask #4
0.0 / 19.0

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

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 1584 KB Correct.
2 Correct 23 ms 1712 KB Correct.
3 Correct 22 ms 1720 KB Correct.
4 Correct 21 ms 4252 KB Correct.
5 Correct 24 ms 1236 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 1644 KB Correct.
2 Correct 18 ms 1580 KB Correct.
3 Correct 41 ms 29156 KB Correct.
4 Correct 14 ms 3088 KB Correct.
5 Correct 21 ms 1364 KB Correct.
6 Correct 23 ms 1680 KB Correct.

Subtask #7
0.0 / 29.0

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

Subtask #8
0.0 / 3.0

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