Submission #1130392

#	Time	Username	Problem	Language	Result	Execution time	Memory
1130392		AlgorithmWarrior	Cyberland (APIO23_cyberland)	C++20	44 / 100	3094 ms	9544 KiB

cyberland

#include <bits/stdc++.h>

using namespace std;

long double const EPS=1e-6;

struct per{
    int nod,dist;
};

struct len{
    int nod;
    long double dist;
};

class cmp{
public:
    bool operator()(len a,len b){
        return a.dist>b.dist;
    }
};

double solve(int N,int M,int K,int H,vector<int>x,vector<int>y,vector<int>c,vector<int>arr){
    vector<bool>viz;
    viz.resize(N+5,0);
    vector<vector<per>>G;
    G.resize(N+5);
    int i;
    int sz=x.size();
    for(i=0;i<sz;++i){
        G[x[i]].push_back({y[i],c[i]});
        G[y[i]].push_back({x[i],c[i]});
    }
    queue<int>q;
    q.push(0);
    viz[0]=1;
    viz[H]=1;
    while(!q.empty()){
        int curr=q.front();
        q.pop();
        for(auto vec : G[curr])
            if(!viz[vec.nod]){
                viz[vec.nod]=1;
                q.push(vec.nod);
            }
    }
    vector<long double>before;
    before.resize(N+5,-1);
    priority_queue<len,vector<len>,cmp>pq;
    for(i=0;i<N;++i)
    if(arr[i]==0 && viz[i]==1)
        pq.push({i,0});
    pq.push({0,0});
    while(!pq.empty()){
        len curr=pq.top();
        pq.pop();
        int nod=curr.nod;
        long double dist=curr.dist;
        if(before[nod]!=-1)
            continue;
        before[nod]=dist;
        for(auto vec : G[nod]){
            int nd=vec.nod;
            long double dst=vec.dist;
            pq.push({nd,dist+dst});
        }
    }
    vector<long double>after;
    after.resize(N+5,-1);
    for(i=0;i<N;++i)
    if(arr[i]==2 && viz[i]==1){
        int j;
        long double dist=before[i];
        for(j=1;j<=K;++j)
            dist/=2;
        pq.push({i,dist});
    }
    while(!pq.empty()){
        len curr=pq.top();
        pq.pop();
        int nod=curr.nod;
        long double dist=curr.dist;
        if(after[nod]!=-1)
            continue;
        after[nod]=dist;
        for(auto vec : G[nod]){
            int nd=vec.nod;
            long double dst=vec.dist;
            pq.push({nd,dist+dst});
        }
    }
    if(before[H]==-1)
        return -1;
    if(after[H]==-1)
        return before[H];
    if(before[H]<after[H])
        return before[H];
    else
        return after[H];
}

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