oj.uz

Submission #926811

# Submission time Handle Problem Language Result Execution time Memory
926811 2024-02-13T20:08:00 Z lumid Cyberland (APIO23_cyberland) C++17
68 / 100
 3000 ms 1340548 KB 
// 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<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;

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<2>(q.top()));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 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){
    // THIS PROBLEM IS 0-INDEXED
    n=N,m=M,k=min(70,K),h=H;
    arri=arr;
    init();

    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});
        }
    }*/

    dfs(0);
    //can.pb(0);
    if(!visited[h])return -1;
    dijkInit();
    dijkstra();

    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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 860 KB Correct.
2 Correct 43 ms 548 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 292 ms 7088 KB Correct.
2 Correct 342 ms 6828 KB Correct.
3 Correct 342 ms 6936 KB Correct.
4 Correct 355 ms 6888 KB Correct.
5 Correct 362 ms 7048 KB Correct.
6 Correct 790 ms 63368 KB Correct.
7 Correct 1053 ms 61668 KB Correct.
8 Correct 363 ms 125804 KB Correct.
9 Correct 215 ms 1908 KB Correct.
10 Correct 202 ms 2132 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 310 ms 6940 KB Correct.
2 Correct 296 ms 7028 KB Correct.
3 Correct 274 ms 7008 KB Correct.
4 Correct 205 ms 1852 KB Correct.
5 Correct 214 ms 1872 KB Correct.
6 Correct 120 ms 49040 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1004 ms 434508 KB Correct.
2 Correct 540 ms 8496 KB Correct.
3 Correct 485 ms 8640 KB Correct.
4 Correct 508 ms 8312 KB Correct.
5 Correct 355 ms 2128 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 258 ms 7492 KB Correct.
2 Correct 301 ms 7044 KB Correct.
3 Correct 294 ms 7300 KB Correct.
4 Correct 607 ms 65344 KB Correct.
5 Correct 167 ms 1256 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 286 ms 7300 KB Correct.
2 Correct 254 ms 6912 KB Correct.
3 Correct 1627 ms 430244 KB Correct.
4 Correct 316 ms 48648 KB Correct.
5 Correct 197 ms 1360 KB Correct.
6 Correct 289 ms 7396 KB Correct.

Subtask #7
0.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 550 ms 9068 KB Correct.
2 Correct 96 ms 13440 KB Correct.
3 Correct 1901 ms 344192 KB Correct.
4 Correct 1331 ms 93792 KB Correct.
5 Execution timed out 3052 ms 512032 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1375 ms 20764 KB Correct.
2 Correct 304 ms 30652 KB Correct.
3 Execution timed out 3076 ms 1340548 KB Time limit exceeded
4 Halted 0 ms 0 KB -