oj.uz

Submission #990478

# Submission time Handle Problem Language Result Execution time Memory
990478 2024-05-30T13:38:08 Z AlphaMale06 Cyberland (APIO23_cyberland) C++17
44 / 100
 32 ms 11612 KB 
#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.0 / 5.0

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

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 4188 KB Correct.
2 Correct 21 ms 4184 KB Correct.
3 Correct 20 ms 4188 KB Correct.
4 Correct 20 ms 4188 KB Correct.
5 Correct 21 ms 4188 KB Correct.
6 Correct 18 ms 4956 KB Correct.
7 Correct 24 ms 4996 KB Correct.
8 Correct 12 ms 5724 KB Correct.
9 Correct 18 ms 4232 KB Correct.
10 Correct 23 ms 4224 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 4440 KB Correct.
2 Correct 20 ms 5212 KB Correct.
3 Correct 18 ms 4688 KB Correct.
4 Correct 19 ms 4956 KB Correct.
5 Correct 19 ms 5128 KB Correct.
6 Correct 5 ms 4956 KB Correct.

Subtask #4
0.0 / 19.0

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

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 4440 KB Correct.
2 Correct 20 ms 4184 KB Correct.
3 Correct 20 ms 4184 KB Correct.
4 Correct 20 ms 5212 KB Correct.
5 Correct 15 ms 4184 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 4188 KB Correct.
2 Correct 15 ms 5208 KB Correct.
3 Correct 32 ms 11612 KB Correct.
4 Correct 14 ms 5720 KB Correct.
5 Correct 18 ms 4952 KB Correct.
6 Correct 17 ms 5236 KB Correct.

Subtask #7
0.0 / 29.0

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

Subtask #8
0.0 / 3.0

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