Submission #927021

#	Time	Username	Problem	Language	Result	Execution time	Memory
927021		lumid	Cyberland (APIO23_cyberland)	C++17	68 / 100	3071 ms	1337520 KiB

cyberland

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

#include <chrono>
#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<int> arri;

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

vector<vector<ll>> dfsadj;
vector<bool> visited;
vector<ll> can;

vector<bool> inqueue;

void init(){
    adj.clear();
    dist.clear();
    processed.clear();
    dfsadj.clear();
    visited.clear();
    can.clear();
    for(int i=0;i<=(k+1)*n;i++){
        dfsadj.pb({});
        adj.pb({});
        visited.pb(0);
    }
}

void dijkInit(){
    dist.clear();
    processed.clear();
    for(int i=0;i<=(k+1)*n;i++){
        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<tuple<ll,double,ll>> q;
    for(ll u:can){
        if(u==h)continue;
        q.push({0,0,-u});
        dist[u]=0;
    }
    q.push({0,0,0});
    dist[0]=0;
    while(!q.empty()){
        owo(get<0>(q.top()));owo(' ');
        owo(get<1>(q.top()));owo(' ');
        owo(get<2>(q.top()));owo(' ');
        owo(q.size());owo('\n');
        ll u=-1*(get<0>(q.top()))*n-get<2>(q.top());q.pop();
        //owo("u: ");owo(u);owo('\n');
        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({-((v-(v%n))/n),-dist[v],-(v%n)});
                //owo(-((v-(v%n))/n));owo(' ');owo(-dist[v]);owo(' ');owo(v%n);owo('\n');
            }
        }
        //owo('\n');
    }
}

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

void spfa(){
    deque<ll> q;
    dist[0]=0;
    inqueue[0]=1;
    q.push_back(0);
    while(!q.empty()){
        ll u=q.front();q.pop_front();
        owo(u);owo('\n');
        inqueue[u]=0;
        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;
                if(!inqueue[v]){
                    //q.push(v);
                    inqueue[v]=1;
                    // magic happens here
                    if(q.size()&&dist[v]<dist[q.front()])
                        q.push_front(v);
                    else q.push_back(v);
                }
            }
        }
    }
}

void dfs(ll u){
    if(visited[u])return;
    visited[u]=1;
    if(u==h)return;
    if(arri[u]==0)can.pb(u);
    for(ll v:dfsadj[u])dfs(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){
    #ifdef reimufumo
    auto chrono_begin = chrono::steady_clock::now();
    #endif

    // THIS PROBLEM IS 0-INDEXED
    n=N,m=M,k=min(70,K),h=H;
    arri=arr;
    init();
    
    #ifdef reimufumo
    cerr << "chrono: " << 1e-6L * chrono::duration_cast<chrono::microseconds>(chrono::steady_clock::now() - chrono_begin).count() << 's' << '\n';
    #endif

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

            if(v!=h && typ1==2) adj[j*n+v].pb({(j+1)*n+u,w,2});
            if(u!=h && typ2==2) adj[j*n+u].pb({(j+1)*n+v,w,2});
        }
        if(v!=h && typ1==0) adj[k*n+v].pb({k*n+u,0,0});
        else if(v!=h) adj[k*n+v].pb({k*n+u,w,1});
        if(u!=h && typ2==0) adj[k*n+u].pb({k*n+v,0,0});
        else if(u!=h) 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});
        }
    }*/

    #ifdef reimufumo
    cerr << "chrono: " << 1e-6L * chrono::duration_cast<chrono::microseconds>(chrono::steady_clock::now() - chrono_begin).count() << 's' << '\n';
    #endif

    dfs(0);
    //can.pb(0);
    if(!visited[h])return -1;
    
    #ifdef reimufumo
    cerr << "chrono: " << 1e-6L * chrono::duration_cast<chrono::microseconds>(chrono::steady_clock::now() - chrono_begin).count() << 's' << '\n';
    #endif

    //dijkInit();
    //dijkstra();
    spfaInit();
    spfa();

    double ans=INF;
    for(int i=0;i<=k;i++){
        ans=min(ans,dist[i*n+h]);
    }
    return (ans>=1e12?-1:ans); // beware of double precision
}

#ifdef reimufumo

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

    vector<double> checklater;
    ll tctc;cin>>tctc;
    while(tctc--){


        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);
        }
        double ans=solve(ninp,minp,kinp,hinp,xinp,yinp,cinp,arrinp);
        cout<<ans<<'\n';
        checklater.pb(ans);

        /*for(int i=0;i<=3;i++){
            for(int j=0;j<n;j++){
                cerr<<dist[i*n+j]<<' ';
            }cerr<<'\n';
        }*/
    }
    cout<<'\n';
    ll counting=0;
    for(double cl:checklater){
        counting++;
        double cn;cin>>cn;
        if(abs(cl-cn)>1){
            cout<<counting<<": "<<cl<<' '<<cn<<'\n';
        }
    }
}

#endif

• 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: 0 / 29
• Subtask 8: 0 / 3