Submission #859870

#	Time	Username	Problem	Language	Result	Execution time	Memory
859870		leanchec	Cyberland (APIO23_cyberland)	C++17	0 / 100	3059 ms	73044 KiB

cyberland

#include<bits/stdc++.h>
using namespace std;

vector<pair<int,int>> adj[100100];
bool visited[100100]={};

void dfs(int cur, int H){
    visited[cur]=true;
    for(int i=0; i<(int)adj[cur].size(); i++){
        int viz=adj[cur][i].first;
        int w=adj[cur][i].second;
        if(visited[viz] || viz==H)continue;
        dfs(viz, H);
    }
}

double solve(int N, int M, int K, int H, vector<int> x, vector<int>
y, vector<int> c, vector<int> arr){
    for(int i=0; i<N; i++){
        visited[i]=0;
        adj[i].clear();
    }
    for(int i=0; i<M; i++){
        adj[x[i]].push_back({y[i], c[i]});
        adj[y[i]].push_back({x[i], c[i]});
    }

    dfs(0, H);

    double dist[100100][75]={}, po[75]={};
    bool achou[100100][75]={};

    for(int i=0; i<N; i++){
        for(int j=0; j<=min(K, 70); j++){
            dist[i][j]=1e17;
        }
    }

    po[0]=1;
    for(int i=0; i<=70; i++)po[i]=po[i-1]*2;

    priority_queue<pair<double, pair<int, int>>, vector<pair<double, pair<int,int>>>, greater<pair<double, pair<int,int>>>> pq;

    pq.push({0, {H, 0}});
    dist[H][0]=0;

    while(!pq.empty()){
        pair<double, pair<int,int>> curtop=pq.top();
        pq.pop();

        int cur=curtop.second.first;
        double curdist=curtop.first;
        int curk=curtop.second.second;

        if(cur==0 || arr[cur]==0 || curk==70){
            return curdist;
        }

        if(achou[cur][curk])continue;
        achou[cur][curk]=true;

        for(int i=0; i<(int)adj[cur].size(); i++){
            int viz=adj[cur][i].first;
            if(viz==H)continue;
            double w=adj[cur][i].second;
            if(arr[cur]==2 && curk+1<=K){
                if(dist[viz][curk+1]>dist[cur][curk]+w/po[curk+1]){
                    dist[viz][curk+1]=dist[cur][curk]+w/po[curk+1];
                    pq.push({dist[viz][curk+1], {viz, curk+1}});
                }
            }
            else if(dist[viz][curk]>dist[cur][curk]+w/po[curk]){
                dist[viz][curk]=dist[cur][curk]+w/po[curk];
                pq.push({dist[viz][curk], {viz, curk}});
            }
        }
    }

    return -1;
}

Compilation message (stderr)

cyberland.cpp: In function 'void dfs(int, int)':
cyberland.cpp:11:13: warning: unused variable 'w' [-Wunused-variable]
   11 |         int w=adj[cur][i].second;
      |             ^

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