Submission #972642

#	Time	Username	Problem	Language	Result	Execution time	Memory
972642		aykhn	Cyberland (APIO23_cyberland)	C++17	15 / 100	3062 ms	24612 KiB

cyberland

#include "cyberland.h"
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
 
#define OPT ios_base::sync_with_stdio(0); \
            cin.tie(0); \
            cout.tie(0)
 
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pid pair<int,double>
#define pld pair<ll,double>
#define pdi pair<double,int>
#define endl "\n"
#define all(v) v.begin(), v.end()
#define mpr make_pair
#define pb push_back
#define ts to_string
#define fi first
#define se second
#define inf 0x3F3F3F3F
#define bpc __builtin_popcount
#define inf 0x3F3F3F3F
#define infll 0x3F3F3F3F3F3F3F3FLL
#define print(v) for(int i = 0; i < v.size(); i++) cout << v[i] << " "; cout<<endl;
 
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<vector<pld>> adj(n);
 
    for (ll i = 0; i < m; i++)
    {
        adj[x[i]].pb(mpr(y[i], c[i]));
        adj[y[i]].pb(mpr(x[i], c[i]));
    }
 
    vector<vector<double>> dist(n, vector<double> (K + 1, -1));
    priority_queue< pair<double, pll>, vector< pair<double, pll> >, greater< pair<double, pll> > > pq;
    vector<int> u(n, 0);
    u[0] = 1;
    queue<int> q;
    while (!q.empty())
    {
        int f = q.front();
        q.pop();
        for (pld &v : adj[f])
        {
            if (u[v.fi]) continue;
            u[v.fi] = 1;
            q.push(v.fi);
        }
    }
    for (int i = 0; i < n; i++)
    {
        if (u[i] && (!i || arr[i] == 0))
        {
            dist[i][0] = 0;
            pq.push(mpr(0, mpr(0, i)));
        }
    }
 
    while (!pq.empty())
    {
        double d = pq.top().fi;
        ll k = pq.top().se.fi;
        ll from = pq.top().se.se;
        pq.pop();
        if (from == h) continue;
      	if (d > dist[from][k]) continue;
        for (ll i = 0; i < adj[from].size(); i++)
        {
            ll to = adj[from][i].fi;
            double w = adj[from][i].se;
            if (arr[to] == 1 || arr[to] == 2)
            {
                if (dist[to][k] > d + w || dist[to][k] == -1)
                {
                    dist[to][k] = d + w;
                    pq.push(mpr(dist[to][k], mpr(k, to)));
                }
            }
            // else if (arr[to] == 0)
            // {
            //     if (dist[to][k] > 0 || dist[to][k] == -1)
            //     {
            //         dist[to][k] = 0;
            //         pq.push(mpr(dist[to][k], mpr(k, to)));
            //     }
            // }
            if (k < K && arr[to] == 2)
            {
                if (dist[to][k + 1] > (d + w)/2 || dist[to][k + 1] == -1)
                {
                    dist[to][k + 1] = (d + w)/2;
                    pq.push(mpr(dist[to][k + 1], mpr(k + 1, to)));
                }
            }
        }
    }
    double res = -1;
    for (ll i = 0; i <= K; i++)
    {
        if (dist[h][i] == -1) continue;
 
        if (res == -1) res = dist[h][i];
        else res = min(res, dist[h][i]);
    }
    return res;
}

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:74:26: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, double> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |         for (ll i = 0; i < adj[from].size(); i++)
      |                        ~~^~~~~~~~~~~~~~~~~~

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