Submission #990477

#	Time	Username	Problem	Language	Result	Execution time	Memory
990477		AlphaMale06	Cyberland (APIO23_cyberland)	C++17	15 / 100	25 ms	12560 KiB

cyberland

#include <bits/stdc++.h>
#include "cyberland.h"

using namespace std;

using ld = long double;
using ll = long long;
#define F first
#define S second

const int N = 1e5+3;
bool mark[N], reachable[N];
vector<int> tp;
vector<pair<int, int>> g[N];
vector<int> z;
vector<int> d;
priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;
ll ds[N], df[N];

void dfs(int v, int h){
    mark[v]=1;
   // if(v==h)return;
    if(tp[v]==0)z.push_back(v);
    if(tp[v]==2)d.push_back(v);
    for(auto to : g[v]){
        if(!mark[to.F])dfs(to.F, h);
    }
}

double solve(int n, int m, int k, int h, vector<int> x, vector<int> y, vector<int> c, vector<int> arr) {
    z.clear();
    d.clear();
    for(int i=0; i< n; i++){
        g[i].clear();
        mark[i]=0;
        reachable[i]=0;
    }
    tp = arr;
    for(int i=0; i< m; i++){
        g[x[i]].push_back({y[i], c[i]});
        g[y[i]].push_back({x[i], c[i]});
    }
    dfs(0, h);
    if(!mark[h]){
        return -1;
    }
    for(int i=0; i< n; i++)reachable[i]=mark[i];
    for(int i=0; i< n; i++){
        mark[i]=0;
        ds[i]=1e18;
    }
    pq.push({0, 0});
    for(int e : z){
        pq.push({e, 0});
        ds[e]=0;
    }
    ds[0]=0;
    while(pq.size()){
        auto dv = pq.top();
        pq.pop();
        if(mark[dv.S])continue;
        mark[dv.S]=1;
        for(auto to : g[dv.S]){
            if(dv.F+to.S<ds[to.F] && reachable[to.F]){
                ds[to.F]=dv.F+to.S;
                pq.push({ds[to.F], to.F});
            }
        }
    }
    for(int i=0; i< n; i++){
        mark[i]=0;
        df[i]=1e18;
    }
    pq.push({0, h});
    df[h]=0;
    while(pq.size()){
        auto dv = pq.top();
        pq.pop();
        if(mark[dv.S])continue;
        mark[dv.S]=1;
        for(auto to : g[dv.S]){
            if(dv.F+to.S<df[to.F] && reachable[to.F]){
                df[to.F]=dv.F+to.S;
                pq.push({df[to.F], to.F});
            }
        }
    }
    ll ans = 1e18;
    for(int i=0; i< n; i++){
        if(arr[i]==0 || i==0)ans=min(ans, df[i]);
    }
    return ans;
}

• Subtask 1: 0 / 5
• Subtask 2: 8 / 8
• Subtask 3: 0 / 13
• Subtask 4: 0 / 19
• Subtask 5: 7 / 7
• Subtask 6: 0 / 16
• Subtask 7: 0 / 29
• Subtask 8: 0 / 3