Submission #380286

#	Time	Username	Problem	Language	Result	Execution time	Memory
380286		Pichon5	Shortcut (IOI16_shortcut)	C++17	0 / 100	2 ms	492 KiB

shortcut

#include "shortcut.h"
#include<bits/stdc++.h>
#define lcm(a,b) (a/__gcd(a,b))*b
#define fast ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define ll long long int
#define vi vector<int>
#define vll vector<ll>
#define pb push_back
#define F first
#define S second
#define mp make_pair
//salida rapida "\n"
//DECIMALES fixed<<sp(n)<<x<<endl;
//gcd(a,b)= ax + by
//lCB x&-x
//set.erase(it) - ersases the element present at the required index//auto it = s.find(element)
//set.find(element) - iterator pointing to the given element if it is present else return pointer pointing to set.end()
//set.lower_bound(element) - iterator pointing to element greater than or equal to the given element
//set.upper_bound(element) - iterator pointing to element greater than the given element
// | ^
//__builtin_popcount(x)
using namespace std;

long long find_shortcut(int n, vi l, vi d, int c){
    vector<vector<pair<int,int> > >G(22,vector<pair<int,int> >());
    vector<bool>vis(22,false);
    vector<bool>ok(22,false);
    for(int i=0;i<n-1;i++){
        G[i].pb({i+1,l[i]});
        G[i+1].pb({i,l[i]});
    }
    for(int i=0;i<n;i++){
        ok[i]=ok[i+10]=1;
        G[10+i].pb({i,d[i]});
        G[i].pb({10+i,d[i]});
    }
    ll res=1e18;
    for(int i=0;i<n;i++){
        for(int l=i+1;l<n;l++){
            int a=i,b=l;
            ll diametro=0;
            for(int j=0;j<=22;j++){
                if(ok[j]==false)continue;
                priority_queue<pair<ll,int> >q;
                vll dis(22,1e18);
                dis[j]=0;
                q.push({0,j});
                vis.assign(22,false);
                while(!q.empty()){
                    int u=q.top().S;
                    q.pop();
                    if(vis[u])continue;
                    vis[u]=1;
                    if(u==a){
                        if(dis[u]+c<=dis[b]){
                            dis[b]=dis[u]+c;
                            q.push({-dis[b],b});
                        }
                    }
                    if(u==b){
                        if(dis[u]+c<=dis[a]){
                            dis[a]=dis[u]+c;
                            q.push({-dis[a],a});
                        }
                    }
                    for(auto it : G[u]){
                        if(dis[u]+it.S<dis[it.F]){
                            dis[it.F]=dis[u]+it.S;
                            q.push({-dis[it.F],it.F});
                        }
                    }
                }
                ll ma=0;
                for(int k=0;k<22;k++){
                    if(ok[k])ma=max(ma,dis[k]);
                }
                diametro=max(diametro, ma);
            }
            //cout<<i<<"  "<<l<<"  "<<diametro<<endl;
            res=min(diametro,res);
        }
    }
    return res;
    //9 30 10 10 10 10 10 10 10 10 20 0 30 0 0 40 0 40 0
    //4 10 10 20 20 0 40 0 30
}

• Subtask 1: 0 / 9
• Subtask 2: 0 / 14
• Subtask 3: 0 / 8
• Subtask 4: 0 / 7
• Subtask 5: 0 / 33
• Subtask 6: 0 / 22
• Subtask 7: 0 / 4
• Subtask 8: 0 / 3