Submission #770177

#	Time	Username	Problem	Language	Result	Execution time	Memory
770177		gg123_pe	Cyberland (APIO23_cyberland)	C++17	97 / 100	661 ms	68316 KiB

cyberland

#include <bits/stdc++.h> 
#include "cyberland.h"

using namespace std; 

#define f(i,a,b) for(int i = a; i < b; i++)
typedef pair <double, pair<int, int>> ii; 

const int N = 1e5 + 5; 
const double inf = 2e15; 

int n, k; 
double d[N][71]; 
bool vis[N]; 
vector <pair<int, double>> adj[N], adj_H; 
vector <int> ARR; 

void check(int u){
    vis[u] = 1; 
    for(auto p: adj[u]){
        int v = p.first; 
        if(!vis[v]) check(v); 
    }
}
void clear(){
    adj_H.clear(); ARR.clear();  
    f(i,0,n) adj[i].clear(), vis[i] = 0;
}
void dij(){
    priority_queue <ii, vector <ii>, greater <ii>> q; 
    f(i,0,n) {
        f(j,0,k+1) d[i][j] = inf; 
        if((ARR[i] == 0 or i == 0) and vis[i]){
            f(j,0,k+1) {
                d[i][j] = 0; 
                q.push({0, {j, i}}); 
            }
        }
    }

    while(!q.empty()){
        auto pa = q.top(); q.pop(); 
        double d_u = pa.first; int u = pa.second.second; int c = pa.second.first;  

        if(d[u][c] != d_u) continue; 
        for(auto p: adj[u]){
            int v = p.first; double w = p.second; 
            if(d[v][c] > d[u][c] + w){
                d[v][c] = d[u][c] + w; 
                q.push({d[v][c], {c, v}}); 
            }
            if(ARR[v] == 2 and c+1 <= k){
                double val = (d[u][c] + w) / 2;  
                if(d[v][c+1] > val){
                    d[v][c+1] = val; 
                    q.push({d[v][c+1], {c+1, v}}); 
                }
            }
        }
    }
}
double solve(int Ni, int M, int K, int H, vector<int> x, vector<int> y, vector<int> c, vector<int> arr) {
    n = Ni; 
    ARR = arr; 
    k = min(60, K); 

    f(i,0,M){
        if(x[i] == H or y[i] == H){
            adj_H.push_back({x[i] + y[i] - H, c[i]}); 
        }
        else {
            adj[x[i]].push_back({y[i], c[i]}); 
            adj[y[i]].push_back({x[i], c[i]}); 
        }
    }
    check(0); 
    dij(); 
    
    double ans = inf; 
    for(auto p: adj_H) {
        int v = p.first; double w = p.second; 
        if(vis[v]) f(i,0,k+1) ans = min(ans, d[v][i] + w); 
    }
    clear(); 
    return (ans == inf) ? -1 : ans;
}

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