oj.uz

Submission #980351

# Submission time Handle Problem Language Result Execution time Memory
980351 2024-05-12T05:48:55 Z thelegendary08 Cyberland (APIO23_cyberland) C++17
44 / 100
 37 ms 11604 KB 
#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.0 / 5.0

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

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 628 KB Correct.
2 Correct 27 ms 604 KB Correct.
3 Correct 25 ms 604 KB Correct.
4 Correct 27 ms 604 KB Correct.
5 Correct 27 ms 604 KB Correct.
6 Correct 22 ms 1692 KB Correct.
7 Correct 37 ms 1692 KB Correct.
8 Correct 14 ms 2908 KB Correct.
9 Correct 28 ms 348 KB Correct.
10 Correct 24 ms 348 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 596 KB Correct.
2 Correct 26 ms 1368 KB Correct.
3 Correct 25 ms 1364 KB Correct.
4 Correct 27 ms 1372 KB Correct.
5 Correct 26 ms 1672 KB Correct.
6 Correct 5 ms 1628 KB Correct.

Subtask #4
0.0 / 19.0

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

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 628 KB Correct.
2 Correct 25 ms 568 KB Correct.
3 Correct 24 ms 632 KB Correct.
4 Correct 23 ms 1524 KB Correct.
5 Correct 22 ms 528 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 604 KB Correct.
2 Correct 21 ms 1508 KB Correct.
3 Correct 34 ms 11604 KB Correct.
4 Correct 15 ms 1976 KB Correct.
5 Correct 24 ms 1412 KB Correct.
6 Correct 23 ms 1372 KB Correct.

Subtask #7
0.0 / 29.0

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

Subtask #8
0.0 / 3.0

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