oj.uz

Submission #990470

# Submission time Handle Problem Language Result Execution time Memory
990470 2024-05-30T13:32:37 Z AlphaMale06 Cyberland (APIO23_cyberland) C++17
15 / 100
 24 ms 9304 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});
            }
        }
    }
    ld ans = ds[h];
    return ds[h];
}

Compilation message

cyberland.cpp: In function 'double solve(int, int, int, int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
cyberland.cpp:88:8: warning: unused variable 'ans' [-Wunused-variable]
   88 |     ld ans = ds[h];
      |        ^~~

Subtask #1
0.0 / 5.0

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

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 4956 KB Correct.
2 Correct 21 ms 5208 KB Correct.
3 Correct 20 ms 5312 KB Correct.
4 Correct 20 ms 5176 KB Correct.
5 Correct 21 ms 5224 KB Correct.
6 Correct 20 ms 5720 KB Correct.
7 Correct 24 ms 5980 KB Correct.
8 Correct 15 ms 6236 KB Correct.
9 Correct 19 ms 4952 KB Correct.
10 Correct 17 ms 4992 KB Correct.

Subtask #3
0.0 / 13.0

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

Subtask #4
0.0 / 19.0

# Verdict Execution time Memory Grader output
1 Incorrect 20 ms 9304 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 5120 KB Correct.
2 Correct 20 ms 5468 KB Correct.
3 Correct 19 ms 5208 KB Correct.
4 Correct 20 ms 6296 KB Correct.
5 Correct 16 ms 4952 KB Correct.

Subtask #6
0.0 / 16.0

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

Subtask #7
0.0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 17 ms 5212 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 5212 KB Wrong Answer.
2 Halted 0 ms 0 KB -