Submission #806417

#	Time	Username	Problem	Language	Result	Execution time	Memory
806417		irmuun	Cyberland (APIO23_cyberland)	C++17	Compilation error	0 ms	0 KiB

cyberland

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

using namespace std;

#define ll long long
#define pb push_back
#define ff first
#define ss second
#define all(s) s.begin(),s.end()
#define rall(s) s.rbegin(),s.rend()

const double inf=1e18;

struct dsu {
    int pa[100001];
	void init(int n) { iota(pa, pa + n + 1, 0); }
	int find(int x) { return pa[x] = (pa[x] == x ? x : find(pa[x])); }
	bool uni(int p, int q) {
		p = find(p);
		q = find(q);
		if (p == q)
			return 0;
		pa[q] = p;
		return 1;
	}
}ds;

double solve(int N, int M, int K, int H, vector<int>x, vector<int>y, vector<int>c, vector<int>arr){
    K=min(K,70);
    vector<double>pw(K+1);
    ds.init(N);
    vector<pair<int,int>>adj[N];
    for(int i=0;i<M;i++){
        if(x[i]!=H&&y[i]!=H){
            ds.uni(x[i],y[i]);
        }
        adj[x[i]].pb({c[i],y[i]});
        adj[y[i]].pb({c[i],x[i]});
    }
    pw[0]=1;
    for(int i=1;i<=K;i++){
        pw[i]=pw[i-1]/2;
    }
    arr[0]=0;
    vector<vector<double>>dist(K+1,vector<double>(N,inf));
    using node=tuple<double,int,int>;
    priority_queue<node,vector<node>,greater<node>>pq;
    auto ck=[&](int k,int x,double d){
        if(dist[k][x]>d){
            dist[k][x]=d;
            pq.push({d,k,x});
        }
    };
    ck(K,H,0);
    while(!pq.empty()){
        auto [d,k,x]=pq.top();
        pq.pop();
        if(dist[k][x]<d){
            continue;
        }
        if(arr[x]==0){
            return d;
        }
        for(auto [c,y]:adj[x]){
            if(ds.find(y)!=ds.find(0)){
                continue;
            }
            ck(k,y,d+c*pw[K-k]);
            if(arr[y]==2&&k>0){
                ck(k-1,y,d+c*pw[K-k+1]);
            }
        }
    }
    return -1;

Compilation message (stderr)

cyberland.cpp: In function 'double solve(int, int, int, int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
cyberland.cpp:75:14: error: expected '}' at end of input
   75 |     return -1;
      |              ^
cyberland.cpp:29:99: note: to match this '{'
   29 | double solve(int N, int M, int K, int H, vector<int>x, vector<int>y, vector<int>c, vector<int>arr){
      |                                                                                                   ^