oj.uz

Submission #981516

# Submission time Handle Problem Language Result Execution time Memory
981516 2024-05-13T09:36:26 Z 8pete8 Cyberland (APIO23_cyberland) C++17
97 / 100
 2426 ms 110584 KB 
#include "cyberland.h"
#include<iostream>
#include<stack>
#include<map>
#include<vector>
#include<string>
#include<unordered_map>
#include <queue>
#include<cstring>
#include<limits.h>
#include <cassert>
#include<cmath>
#include<set>
#include<algorithm>
#include <iomanip>
#include<numeric> //gcd(a,b)
#include<bitset>
#include <cstdlib> 
#include <cstdint>
using namespace std;
#define ll long long
#define f first
//#define endl "\n"
#define s second
#define pii pair<int,int>
#define ppii pair<int,pii>
#define vi vector<int>
#define pb push_back
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define F(n) for(int i=0;i<n;i++)
#define lb lower_bound
#define ub upper_bound
#define fastio ios::sync_with_stdio(false);cin.tie(NULL);
#pragma GCC optimize ("03,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
using namespace std;
#define int long long
#define double long double
const int inf=1e18,mxn=1e5;
double pre=1e-7;
struct info{
    double cost;
    int cur,use,bro;
    bool operator<(info a)const{return (cost>a.cost);};
};
vector<pii>adj[mxn+10];
double what[mxn+10][31][2];
double_t solve(int32_t n,int32_t m,int32_t k,int32_t H,vector<int32_t>x,vector<int32_t>y,vector<int32_t>c,vector<int32_t> arr){
    k=min(k,30);
    //why is it passing sub 2 but not sub 3???
    for(int i=0;i<n;i++)adj[i].clear();
    //for(int i=0;i<n;i++)for(int j=0;j<=k;j++)for(int g=0;g<2;g++)dist[i][j][g]=inf;
    for(int i=0;i<m;i++){
        adj[x[i]].pb({y[i],c[i]});
        adj[y[i]].pb({x[i],c[i]});
    }
    adj[H].clear();//cant move
    //double ans=inf;
    for(int i=0;i<n;i++)for(int j=0;j<=k;j++)for(int g=0;g<2;g++)what[i][j][g]=inf;
    what[0][0][0]=0;
    priority_queue<info>pq;
    pq.push({0,0,0,0});
    double ans=inf;
    while(!pq.empty()){
        int cur=pq.top().cur,use=pq.top().use,bro=pq.top().bro;
        double cost=pq.top().cost;
        pq.pop();
        if(cur==H)ans=min(ans,cost);
        if(what[cur][use][bro]<cost)continue;
        if(arr[cur]==2&&use<k&&bro==0){
            double a=(cost*1.0)/2;
            if(what[cur][use+1][1]>a){
                what[cur][use+1][1]=a;
                pq.push((info){what[cur][use+1][1],cur,use+1,1});
            }
        }
        for(auto i:adj[cur]){
            if(what[cur][use][bro]+i.s<what[i.f][use][0]){
                double a=cost+i.s;
                what[i.f][use][0]=a;
                if(arr[i.f]==0)what[i.f][use][0]=0;
                pq.push((info){what[i.f][use][0]*1.0,i.f,use,0});
            }
        }
    }
    if(ans==inf)return -1;
    return ans;
    /*
    dist[0][0][0]=0;
    priority_queue<info>pq;
    pq.push({0,0,0,0});
    for(int i=0;i<n;i++){
        if(arr[i]==0){
            for(int j=0;j<=k;j++)pq.push({0,i,j,0}),dist[i][j][0]=0;
        }
    }
    while(!pq.empty()){
        info cur=pq.top();
        pq.pop();
        if(cur.cur==H)ans=min(ans,cur.cost);
        if(dist[cur.cur][cur.use][cur.bro]!=cur.cost)continue;
        if(arr[cur.cur]==2&&cur.use<k&&cur.bro==0){
            double cost=(cur.cost*1.0/2);
            if(dist[cur.cur][cur.use+1][1]>cost){
                dist[cur.cur][cur.use+1][1]=cost;
                pq.push({cost,cur.cur,cur.use+1,1});
            }
        }
        for(auto i:adj[cur.cur]){
            double a=cur.cost+i.s;
            if(a<dist[i.f][cur.use][0]){
                dist[i.f][cur.use][0]=a;
                pq.push({a,i.f,cur.use,0});
            }
        }
    }
    if(ans==inf)return -1;
    return ans;*/
}
#undef int
/*
int32_t main(){
    int t;cin>>t;
    int n,m,k,h;cin>>n>>m>>k>>h;
    vector<int>x(m),y(m),z(m),arr(n);
    for(int i=0;i<n;i++)cin>>arr[i];
    for(int i=0;i<m;i++)cin>>x[i]>>y[i]>>z[i];
    cout<<solve(n,m,k,h,x,y,z,arr);
}*/
 
/*
1
4 4 30
3
1 1 2 1
0 1 5
0 2 4
1 3 2
2 3 4
*/

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 3408 KB Correct.
2 Correct 22 ms 3420 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 5468 KB Correct.
2 Correct 29 ms 5648 KB Correct.
3 Correct 28 ms 5468 KB Correct.
4 Correct 34 ms 5728 KB Correct.
5 Correct 29 ms 5464 KB Correct.
6 Correct 27 ms 14644 KB Correct.
7 Correct 36 ms 14684 KB Correct.
8 Correct 22 ms 25692 KB Correct.
9 Correct 27 ms 3412 KB Correct.
10 Correct 25 ms 3420 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 5712 KB Correct.
2 Correct 30 ms 5464 KB Correct.
3 Correct 28 ms 5468 KB Correct.
4 Correct 35 ms 3672 KB Correct.
5 Correct 29 ms 3408 KB Correct.
6 Correct 8 ms 12376 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 719 ms 65472 KB Correct.
2 Correct 1177 ms 6528 KB Correct.
3 Correct 1052 ms 6748 KB Correct.
4 Correct 1061 ms 6736 KB Correct.
5 Correct 716 ms 4444 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 5724 KB Correct.
2 Correct 26 ms 5956 KB Correct.
3 Correct 26 ms 5724 KB Correct.
4 Correct 28 ms 15004 KB Correct.
5 Correct 23 ms 3408 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 5724 KB Correct.
2 Correct 27 ms 5788 KB Correct.
3 Correct 54 ms 83720 KB Correct.
4 Correct 20 ms 12828 KB Correct.
5 Correct 24 ms 3416 KB Correct.
6 Correct 25 ms 5724 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 619 ms 7188 KB Correct.
2 Correct 70 ms 8500 KB Correct.
3 Correct 2426 ms 110584 KB Correct.
4 Correct 1955 ms 30828 KB Correct.
5 Correct 1593 ms 96932 KB Correct.
6 Correct 619 ms 72100 KB Correct.
7 Correct 1908 ms 33780 KB Correct.
8 Correct 1853 ms 10320 KB Correct.
9 Correct 525 ms 8100 KB Correct.
10 Correct 567 ms 9028 KB Correct.
11 Correct 1781 ms 7868 KB Correct.
12 Correct 581 ms 8224 KB Correct.
13 Correct 549 ms 8628 KB Correct.
14 Correct 1476 ms 58160 KB Correct.
15 Correct 2074 ms 20004 KB Correct.
16 Correct 552 ms 9288 KB Correct.
17 Correct 687 ms 8288 KB Correct.
18 Correct 677 ms 8340 KB Correct.
19 Correct 2024 ms 10224 KB Correct.
20 Correct 40 ms 3748 KB Correct.
21 Correct 51 ms 6848 KB Correct.
22 Correct 43 ms 10960 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 614 ms 7196 KB Correct.
2 Correct 73 ms 8516 KB Correct.
3 Incorrect 646 ms 110160 KB Wrong Answer.
4 Halted 0 ms 0 KB -