oj.uz

Submission #806430

# Submission time Handle Problem Language Result Execution time Memory
806430 2023-08-04T06:42:51 Z irmuun Cyberland (APIO23_cyberland) C++17
100 / 100
 176 ms 67032 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,70);
    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 22 ms 404 KB Correct.
2 Correct 29 ms 404 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 748 KB Correct.
2 Correct 21 ms 676 KB Correct.
3 Correct 20 ms 740 KB Correct.
4 Correct 20 ms 836 KB Correct.
5 Correct 20 ms 740 KB Correct.
6 Correct 17 ms 3796 KB Correct.
7 Correct 22 ms 3692 KB Correct.
8 Correct 10 ms 7300 KB Correct.
9 Correct 23 ms 620 KB Correct.
10 Correct 20 ms 596 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 680 KB Correct.
2 Correct 24 ms 692 KB Correct.
3 Correct 18 ms 744 KB Correct.
4 Correct 25 ms 496 KB Correct.
5 Correct 20 ms 604 KB Correct.
6 Correct 4 ms 3156 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 20812 KB Correct.
2 Correct 19 ms 704 KB Correct.
3 Correct 18 ms 800 KB Correct.
4 Correct 18 ms 756 KB Correct.
5 Correct 20 ms 496 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 716 KB Correct.
2 Correct 23 ms 672 KB Correct.
3 Correct 24 ms 720 KB Correct.
4 Correct 21 ms 3612 KB Correct.
5 Correct 24 ms 496 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 668 KB Correct.
2 Correct 18 ms 760 KB Correct.
3 Correct 49 ms 27356 KB Correct.
4 Correct 13 ms 2468 KB Correct.
5 Correct 21 ms 480 KB Correct.
6 Correct 19 ms 724 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 716 KB Correct.
2 Correct 3 ms 852 KB Correct.
3 Correct 44 ms 24548 KB Correct.
4 Correct 38 ms 6400 KB Correct.
5 Correct 34 ms 15208 KB Correct.
6 Correct 23 ms 7124 KB Correct.
7 Correct 37 ms 6564 KB Correct.
8 Correct 39 ms 1408 KB Correct.
9 Correct 19 ms 696 KB Correct.
10 Correct 19 ms 704 KB Correct.
11 Correct 40 ms 788 KB Correct.
12 Correct 21 ms 684 KB Correct.
13 Correct 20 ms 732 KB Correct.
14 Correct 39 ms 8180 KB Correct.
15 Correct 36 ms 2532 KB Correct.
16 Correct 20 ms 720 KB Correct.
17 Correct 21 ms 744 KB Correct.
18 Correct 21 ms 688 KB Correct.
19 Correct 45 ms 720 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
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 952 KB Correct.
2 Correct 4 ms 1352 KB Correct.
3 Correct 79 ms 67032 KB Correct.
4 Correct 39 ms 2968 KB Correct.
5 Correct 38 ms 26408 KB Correct.
6 Correct 25 ms 10324 KB Correct.
7 Correct 49 ms 12804 KB Correct.
8 Correct 42 ms 1328 KB Correct.
9 Correct 22 ms 1068 KB Correct.
10 Correct 26 ms 992 KB Correct.
11 Correct 176 ms 588 KB Correct.
12 Correct 29 ms 1044 KB Correct.
13 Correct 29 ms 996 KB Correct.
14 Correct 50 ms 27232 KB Correct.
15 Correct 51 ms 33444 KB Correct.
16 Correct 41 ms 11680 KB Correct.
17 Correct 40 ms 2844 KB Correct.
18 Correct 24 ms 1012 KB Correct.
19 Correct 25 ms 1076 KB Correct.
20 Correct 25 ms 988 KB Correct.
21 Correct 60 ms 972 KB Correct.
22 Correct 3 ms 468 KB Correct.
23 Correct 2 ms 868 KB Correct.
24 Correct 3 ms 1236 KB Correct.