oj.uz

Submission #980361

# Submission time Handle Problem Language Result Execution time Memory
980361 2024-05-12T06:15:42 Z thelegendary08 Cyberland (APIO23_cyberland) C++17
44 / 100
 36 ms 9804 KB 
#include "cyberland.h"
#include<bits/stdc++.h>
#define pb push_back
#define ll long long int
#define vi vector<int>
#define vvi vector<vector<int>>
#define vll vector<long long int>
#define vvll vector<vector<long long int>>
#define pii pair<int, int>
#define vpii vector<pair<int, int>>
#define vpll vector<pair<long long int, long long int>>
#define pqpll priority_queue<pair<long long int, long long int>>
#define vc vector<char>
#define vvc vector<vector<char>>
#define vb vector<bool>
#define mii map<int,int>
#define mll map<long long int, long long int>
#define mivi map<int,vector<int>>
#define f0r(i,n) for(int i=0;i<n;i++)
#define FOR(i,k,n) for(int i=k;i<n;i++)
using namespace std;
const int mxn = 100005;
/*
int h;
void dfs(int x){
    if(rb1[x])return;
    rb1[x] = 1;
    for(auto u : adj[x]){
        if(u.first != h)dfs(u.first);
    }
}
*/
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) {

    bool hastwo = 0;
    f0r(i, N)if(arr[i] == 2)hastwo = 1;
    if(!hastwo){
        vector<vpll> adj(N);
        vb rb1(N);
        //for(auto u : x)cout<<u<<'a';
        //cout<<'\n';
        f0r(i, M){
            adj[x[i]].pb({y[i], c[i]});
            adj[y[i]].pb({x[i], c[i]});
        }
        f0r(i,N){
            //for(auto u : adj[N])cout<<u.first<<' '<<u.second<<' ';
            //cout<<'\n';
        }

        priority_queue<pair<ll,ll>>q;
        vb vis(N, false);
        vb vis2(N, false);

        vll dist1(N, 4e18);
        vll dist2(N, 4e18);
        q.push({0, 0});
        //vis[0] = 1;
        rb1[0] = 1;
        dist1[0] = 0;

        queue<int>que;
        que.push(0);
        while(!que.empty()){
            int cur = que.front();
            que.pop();
            for(auto u : adj[cur]){
                if(rb1[u.first])continue;
                if(u.first == H)continue;
                rb1[u.first] = 1;
                que.push(u.first);
            }
        }






        while(!q.empty()){
            pair<ll,ll>cur = q.top();
            q.pop();
            ll c = cur.second;
            if(vis[c])continue;
            vis[c] = true;
            //cout<<c<<'\n';
            for(auto u : adj[c]){
                ll b = u.first;
                ll w = u.second;
                if(dist1[c] + w < dist1[b]){
                    dist1[b] = dist1[c] + w;
                    q.push({-dist1[b], b});
                }
            }
        }

        q.push({0, H});

        //vis2[H] = 1;
        dist2[H] = 0;
        while(!q.empty()){
            pair<ll,ll>cur = q.top();
            q.pop();
            ll c = cur.second;
            if(vis2[c])continue;
            vis2[c] = 1;
            for(auto u : adj[c]){
                ll b = u.first;
                ll w = u.second;
                if(dist2[c] + w < dist2[b]){
                    dist2[b] = dist2[c] + w;
                    q.push({-dist2[b], b});
                }
            }
        }
        //for(auto u : dist1)cout<<u<<' ';
        //cout<<'\n';
        //for(auto u : dist2)cout<<u<<' ';
        //cout<<'\n';

        if(!vis[H])return -1;
        else{
            ll mn = dist2[0];
            f0r(i, N){
                if(arr[i] == 0 && rb1[i] && vis2[i])mn = min(mn, dist2[i]);
            }
            return mn;
        }
    }
    else{
        ll nxt[N];
        bool d2[N];
        f0r(i, M){
            nxt[x[i]] = c[i];
        }
        long double cur = 0;
        int lsz = 0;
        FOR(i, 1, H){
            if(arr[i] == 0)lsz = i;
        }

        for(int i = H;i>=lsz;i--){
            if(K > 0 && arr[i] == 2){
                d2[i] = 1;
                K--;
            }

        }
        //f0r(i, N)cout<<d2[i]<<' ';
        //cout<<'\n';

        f0r(i, H){
            cur += nxt[i];
            if(arr[i+1] == 0)cur = 0;
            if(d2[i+1])cur/=2.0;
            //cout<<cur<<'\n';
        }
        return cur;
    }

}

Subtask #1
0.0 / 5.0

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

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 600 KB Correct.
2 Correct 26 ms 604 KB Correct.
3 Correct 27 ms 604 KB Correct.
4 Correct 30 ms 856 KB Correct.
5 Correct 26 ms 600 KB Correct.
6 Correct 22 ms 1692 KB Correct.
7 Correct 29 ms 1696 KB Correct.
8 Correct 13 ms 2908 KB Correct.
9 Correct 26 ms 348 KB Correct.
10 Correct 23 ms 348 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 592 KB Correct.
2 Correct 25 ms 600 KB Correct.
3 Correct 24 ms 604 KB Correct.
4 Correct 25 ms 532 KB Correct.
5 Correct 25 ms 532 KB Correct.
6 Correct 5 ms 1572 KB Correct.

Subtask #4
0.0 / 19.0

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

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 604 KB Correct.
2 Correct 24 ms 604 KB Correct.
3 Correct 24 ms 604 KB Correct.
4 Correct 22 ms 1372 KB Correct.
5 Correct 25 ms 620 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 604 KB Correct.
2 Correct 24 ms 856 KB Correct.
3 Correct 36 ms 9804 KB Correct.
4 Correct 15 ms 1460 KB Correct.
5 Correct 25 ms 536 KB Correct.
6 Correct 22 ms 620 KB Correct.

Subtask #7
0.0 / 29.0

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

Subtask #8
0.0 / 3.0

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