Submission #980361

#	Time	Username	Problem	Language	Result	Execution time	Memory
980361		thelegendary08	Cyberland (APIO23_cyberland)	C++17	44 / 100	36 ms	9804 KiB

cyberland

#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 / 5
• Subtask 2: 8 / 8
• Subtask 3: 13 / 13
• Subtask 4: 0 / 19
• Subtask 5: 7 / 7
• Subtask 6: 16 / 16
• Subtask 7: 0 / 29
• Subtask 8: 0 / 3