Submission #980351

#	Time	Username	Problem	Language	Result	Execution time	Memory
980351		thelegendary08	Cyberland (APIO23_cyberland)	C++17	44 / 100	37 ms	11604 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) {
    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;
    }
}

• 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