Submission #1244018

#	Time	Username	Problem	Language	Result	Execution time	Memory
1244018		nvc2k8	Cyberland (APIO23_cyberland)	C++20	97 / 100	3093 ms	329140 KiB

cyberland

#include <bits/stdc++.h>
#include "cyberland.h"
#define TASK "aksdjasd"
#define endl '\n'
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define BIT(i,x) (((i)>>(x))&1)
#define FOR(i,a,b) for(int i = (a); i<=(b); i++)
#define FORD(i,a,b) for(int i = (a); i>=(b); i--)
#define all(C) C.begin(), C.end()
using namespace std;
using ll = long long;
using pii = pair<int,int>;
const int INT_LIM = 2147483647;
const ll LL_LIM = 9223372036854775807;
template <typename X> bool minimize(X &x, const X &y) {if (x>y){x = y; return true;}return false;}
template <typename X> bool maximize(X &x, const X &y) {if (x<y){x = y; return true;}return false;}
///------------------------------------------///
struct DSU{
    int par[100005];
    void init(int n)
    {
        FOR(i, 1, n) par[i] = i;
    }
    int get(int u)
    {
        return (par[u]==u)?u:par[u] = get(par[u]);
    }
    bool merge(int u, int v)
    {
        u = get(u); v = get(v);
        if (u==v) return false;
        par[v] = u; return true;
    }
} dsu;
int n,m,k,h;
vector<pair<int,ll>> adj[100005];
int a[100005];
double dist[100005][205];
const double INF = 1000000000000000000;
const double EPS = 1e-6;

double solve(int N, int M, int K, int H, vector<int> x, vector<int> y, vector<int> c, vector<int> arr) {
    n = N; m = M; k = K; h = H+1;
    dsu.init(n);
    FOR(i, 1, n) adj[i].clear();
    FOR(i, 0, m-1)
    {
        int u = x[i]+1, v = y[i]+1;
        if (u!=h && v!=h) dsu.merge(u,v);
        adj[u].pb(mp(v, c[i]));
        adj[v].pb(mp(u, c[i]));
    }
    FOR(i, 0, n-1) a[i+1] = arr[i];

    k = min(k, 200);
    FOR(i, 1, n) FOR(j, 0, k) dist[i][j] = INF;
    priority_queue<pair<double,pii>, vector<pair<double,pii>>, greater<pair<double,pii>> > q;
    dist[1][0] = 0; q.push(mp(0,mp(1,0)));
    FOR(i, 2, n) if (a[i]==0 && dsu.get(i)==dsu.get(1))
    {
        dist[i][0] = 0; q.push(mp(0, mp(i,0)));
    }

    double ans = INF;
    while (!q.empty())
    {
        int u = q.top().se.fi, cnt = q.top().se.se; double d = q.top().fi;
        q.pop();
        if (dist[u][cnt]<d) continue;
        if (u==h)
        {
            minimize(ans, d);
            continue;
        }

        for (auto V:adj[u])
        {
            int v = V.fi; double w = V.se;
            if (minimize(dist[v][cnt], d+w))
            {
                q.push(mp(d+w, mp(v,cnt)));
            }
            if (a[v]==2 && cnt<k)
            {
                if (minimize(dist[v][cnt+1], (d+w)/2))
                {
                    q.push(mp((d+w)/2, mp(v,cnt+1)));
                }
            }
        }
    }

    if (abs(ans-INF)<EPS) return -1;
    return 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