Submission #926787

#	Time	Username	Problem	Language	Result	Execution time	Memory
926787		lumid	Cyberland (APIO23_cyberland)	C++17	0 / 100	3131 ms	1325012 KiB

cyberland

// Source: https://usaco.guide/general/io

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

typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef long double ld;
typedef pair<ll, ll> pll;
#define FOR(i, a, b) for(int i = a; i < b; i++)
#define ROF(i, a, b) for(int i = a; i >= b; i--)
#define ms memset
#define pb push_back
#define fi first
#define se second
#define inp(n, a) vector<ll> a;for(int i=0;i<n;i++){ll now;cin>>now;a.pb(now);}
#define all(a) a.begin(),a.end()
#define show(a) for(long long loppls=0;loppls<(long long)(a.size()-1);loppls++)cout<<a[loppls]<<' ';cout<<a[a.size()-1];

#ifdef reimufumo
#define owo(x) std::cerr << x;
#define ovo(a) for(long long loppls=0;loppls<(long long)(a.size()-1);loppls++)cerr<<a[loppls]<<' ';cerr<<a[a.size()-1];
#define ouo(a,x) for(long long loppls=0;loppls<x-1;loppls++)cerr<<a[loppls];cerr<<a[x-1];
#define dbg(x) std::cerr << #x << " = " << (x) << " (L" << __LINE__ << ") " << __FILE__ << std::endl
#define dbgif(cond, x) ((cond) ? std::cerr << #x << " = " << (x) << " (L" << __LINE__ << ") " << __FILE__ << std::endl : std::cerr)
#else
#define owo(x) ((void)0)
#define ovo(a) ((void)0)
#define ouo(a,x) ((void)0)
#define dbg(x) ((void)0)
#define dbgif(cond, x) ((void)0)
#endif

long long binpow(long long a, long long b, long long m) {
    a %= m;
    long long res = 1;
    while (b > 0) {
        if (b & 1)
            res = res * a % m;
        a = a * a % m;
        b >>= 1;
    }
    return res;
}

long long inv(long long a, long long p){
    return binpow(a, p-2,  p);
}

vector<ll> fact; // must be init if nCk needed

long long nCk(long long n, long long k, long long p){
    return ((fact[n] * inv(fact[k], p) % p) * inv(fact[n-k], p)) % p;
}

ll sum2(ll a, ll l, ll n){return (n*(a+l))/2;}
ll ceil2(ll a, ll b){ll c=a/b;if(a%b!=0)c++;return c;}
ll floor2(ll x, ll m){ll r=(x%m+m)%m;return (x-r)/m;}

const ll INF=1e16,MAX=100020,MOD=998244353;

ll n,m,k,h;
vector<vector<vector<ll>>> adj; // adj[u] {v,w,type}
vector<double> dist;
vector<bool> processed;

void init(){
    for(int i=0;i<=(k+1)*n;i++){
        adj.pb({});
        dist.pb(INF); // check on this because of the double
        processed.pb(0);
    }
}

double calc(double d,ll w,ll typ){ // todo: calculate distance
    if(typ==1){
        return (double)(d)+(double)(w);
    }else if(typ==0){
        return 0.0;
    }else{
        return (double)(((double)(d)+(double)(w))/2.0);
    }
}

void dijkstra(){
    priority_queue<pair<double,ll>> q;
    q.push({0,0});
    dist[0]=0;
    while(!q.empty()){
        ll u=q.top().se;q.pop();
        if(processed[u])continue;
        processed[u]=1;
        for(vector<ll> node:adj[u]){
            ll v=node[0],w=node[1],typ=node[2];
            double distnow=calc(dist[u],w,typ);
            if(distnow<dist[v]){
                dist[v]=distnow;
                q.push({-dist[v],v});
            }
        }
    }
}

double solve(int N, int M, int K, int H, std::vector<int> x, std::vector<int> y, std::vector<int> c, std::vector<int> arr){
    // THIS PROBLEM IS 0-INDEXED
    n=N,m=M,k=min(200,K),h=H;
    init();

    for(int i=0;i<m;i++){ // whaaaaaaaaat
        ll u=x[i],v=y[i],w=c[i];
        ll typ1=arr[u],typ2=arr[v];
        for(int j=0;j<k;j++){
            if(typ1==0) adj[j*n+v].pb({j*n+u,0,0});
            else adj[j*n+v].pb({j*n+u,w,1});
            
            if(typ2==0) adj[j*n+u].pb({j*n+v,0,0});
            else adj[j*n+u].pb({j*n+v,w,1});

            if(typ1==2) adj[j*n+v].pb({(j+1)*n+u,w,2});
            if(typ2==2) adj[j*n+u].pb({(j+1)*n+v,w,2});
        }
        if(typ1==0) adj[k*n+v].pb({k*n+u,0,0});
        else adj[k*n+v].pb({k*n+u,w,1});
        if(typ2==0) adj[k*n+u].pb({k*n+v,0,0});
        else adj[k*n+u].pb({k*n+v,w,1});
    }

    // rmb to join down fencengtu
    for(int i=0;i<k;i++){
        for(int j=0;j<n;j++){
            adj[i*n+j].pb({(i+1)*n+j,0,1});
        }
    }

    dijkstra();
    return (dist[k*n+h]>=1e12?-1:dist[k*n+h]); // beware of double precision
}


#ifdef reimufumo

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);

    int ninp,minp,kinp,hinp;cin>>ninp>>minp>>kinp>>hinp;
    vector<int> xinp,yinp,cinp,arrinp;
    for(int i=0;i<ninp;i++){
        int arrnow;cin>>arrnow;
        arrinp.pb(arrnow);
    }
    for(int i=0;i<minp;i++){
        int xnow,ynow,cnow;cin>>xnow>>ynow>>cnow;
        xinp.pb(xnow);yinp.pb(ynow);cinp.pb(cnow);
    }
	cout<<solve(ninp,minp,kinp,hinp,xinp,yinp,cinp,arrinp);

    for(int i=0;i<=k;i++){
        for(int j=0;j<n;j++){
            cerr<<dist[i*n+j]<<' ';
        }cerr<<'\n';
    }
}

#endif

• 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