oj.uz

Submission #957939

# Submission time Handle Problem Language Result Execution time Memory
957939 2024-04-04T13:54:46 Z MtSaka Cyberland (APIO23_cyberland) C++17
100 / 100
 2521 ms 175184 KB 
#include "cyberland.h"
#include<bits/stdc++.h>
#define overload(a,b,c,d,...) d
#define rep1(a) for(ll _=0;_<(ll)a;++_)
#define rep2(i,n) for(ll i=0;i<(ll)n;++i)
#define rep3(i,l,r) for(ll i=(ll)l;i<(ll)r;++i)
#define rep(...) overload(__VA_ARGS__,rep3,rep2,rep1)(__VA_ARGS__)
#define rrep1(i,a) for(ll i=(ll)a-1;i>=0;--i)
#define rrep2(i,a,b) for(ll i=(ll)b-1;i>=(ll)a;--i)
#define rrep(...) overload(__VA_ARGS__,rrep2,rrep1)(__VA_ARGS__)
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define pb push_back
#define eb emplace_back
using namespace std;
using ll=long long;
using ull=unsigned long long;
using ld=long double;
template<typename T,typename U>inline bool chmin(T&a,const U&b){return (a>b?a=b,true:false);}
template<typename T,typename U>inline bool chmax(T&a,const U&b){return (a<b?a=b,true:false);}
static constexpr ll inf=numeric_limits<ll>::max()/2;
using vl=vector<ll>;
using ld=long double;
static constexpr ld eps=1e-9;
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){
    chmin(K,100);
    vector<vector<ld>>dist(N,vector<ld>(K+1,inf));
    vector<vector<pair<ll,ll>>>g(N);
    vl vis(N,0);
    rep(i,M){
        g[x[i]].eb(y[i],c[i]);
        g[y[i]].eb(x[i],c[i]);
    }
    auto dfs=[&](auto&&dfs,int v)->void {
        if(v==H)return;
        for(auto [u,c]:g[v]){
            if(vis[u])continue;
            vis[u]=1;
            dfs(dfs,u);
        }
    };
    vis[0]=1;
    dfs(dfs,0);
    if(!vis[H])return -1;
    priority_queue<tuple<ld,ll,ll>,vector<tuple<ld,ll,ll>>,greater<>>pq;
    rep(i,N){
        if(vis[i]&&(i==0||arr[i]==0)){
            dist[i][K]=0;
            pq.emplace(0,i,K);
        }
    }
    rep(i,K+1){
        priority_queue<tuple<ld,ll,ll>,vector<tuple<ld,ll,ll>>,greater<>>npq;
        if(pq.empty())break;
        while(!pq.empty()){
            auto [d,v,k]=pq.top();pq.pop();
            if(dist[v][k]!=d)continue;
            if(v==H)continue;
            for(auto [u,cost]:g[v]){
                if(dist[u][k]>(ld)(d+(ld)cost)){
                    dist[u][k]=(ld)(d+(ld)cost);
                    pq.emplace(dist[u][k],u,k);
                }
                if(k-1>=0&&arr[u]==2&&dist[u][k-1]>(ld)(d+(ld)cost)/2.0){
                    dist[u][k-1]=(ld)(d+(ld)cost)/2.0;
                    npq.emplace(dist[u][k-1],u,k-1);
                }
            }
        }
        pq=move(npq);
    }
    ld res=inf;
    rep(i,K+1)chmin(res,dist[H][i]);
    if(res==inf)return -1;
    return res;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 600 KB Correct.
2 Correct 19 ms 604 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 1088 KB Correct.
2 Correct 29 ms 1116 KB Correct.
3 Correct 28 ms 1108 KB Correct.
4 Correct 31 ms 1112 KB Correct.
5 Correct 29 ms 1164 KB Correct.
6 Correct 28 ms 6816 KB Correct.
7 Correct 35 ms 6560 KB Correct.
8 Correct 18 ms 12892 KB Correct.
9 Correct 27 ms 604 KB Correct.
10 Correct 26 ms 604 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 1112 KB Correct.
2 Correct 30 ms 1112 KB Correct.
3 Correct 28 ms 1112 KB Correct.
4 Correct 29 ms 592 KB Correct.
5 Correct 29 ms 604 KB Correct.
6 Correct 7 ms 5980 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 154 ms 38244 KB Correct.
2 Correct 144 ms 1116 KB Correct.
3 Correct 124 ms 1116 KB Correct.
4 Correct 143 ms 1076 KB Correct.
5 Correct 82 ms 576 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 1112 KB Correct.
2 Correct 26 ms 1116 KB Correct.
3 Correct 26 ms 1324 KB Correct.
4 Correct 29 ms 6404 KB Correct.
5 Correct 23 ms 348 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 1088 KB Correct.
2 Correct 22 ms 1076 KB Correct.
3 Correct 52 ms 48980 KB Correct.
4 Correct 17 ms 4280 KB Correct.
5 Correct 25 ms 592 KB Correct.
6 Correct 25 ms 1076 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 160 ms 952 KB Correct.
2 Correct 26 ms 1372 KB Correct.
3 Correct 803 ms 42580 KB Correct.
4 Correct 380 ms 13252 KB Correct.
5 Correct 845 ms 31540 KB Correct.
6 Correct 301 ms 15104 KB Correct.
7 Correct 362 ms 12784 KB Correct.
8 Correct 265 ms 4172 KB Correct.
9 Correct 128 ms 1852 KB Correct.
10 Correct 118 ms 1984 KB Correct.
11 Correct 243 ms 2844 KB Correct.
12 Correct 144 ms 2104 KB Correct.
13 Correct 154 ms 2140 KB Correct.
14 Correct 348 ms 14616 KB Correct.
15 Correct 335 ms 6276 KB Correct.
16 Correct 141 ms 2012 KB Correct.
17 Correct 162 ms 1980 KB Correct.
18 Correct 147 ms 1872 KB Correct.
19 Correct 366 ms 3012 KB Correct.
20 Correct 8 ms 604 KB Correct.
21 Correct 10 ms 1040 KB Correct.
22 Correct 22 ms 1880 KB Correct.

Subtask #8
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 412 ms 2100 KB Correct.
2 Correct 78 ms 3160 KB Correct.
3 Correct 1381 ms 175184 KB Correct.
4 Correct 451 ms 7180 KB Correct.
5 Correct 2493 ms 70552 KB Correct.
6 Correct 1020 ms 26464 KB Correct.
7 Correct 1041 ms 33668 KB Correct.
8 Correct 391 ms 4456 KB Correct.
9 Correct 335 ms 3124 KB Correct.
10 Correct 299 ms 2912 KB Correct.
11 Correct 245 ms 1548 KB Correct.
12 Correct 391 ms 3304 KB Correct.
13 Correct 388 ms 3072 KB Correct.
14 Correct 2521 ms 71416 KB Correct.
15 Correct 2196 ms 88068 KB Correct.
16 Correct 696 ms 23016 KB Correct.
17 Correct 441 ms 8544 KB Correct.
18 Correct 352 ms 3432 KB Correct.
19 Correct 485 ms 3340 KB Correct.
20 Correct 376 ms 3172 KB Correct.
21 Correct 1099 ms 3980 KB Correct.
22 Correct 18 ms 600 KB Correct.
23 Correct 25 ms 2124 KB Correct.
24 Correct 67 ms 2652 KB Correct.