제출 #415829

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
415829		MeGustaElArroz23	Shortcut (IOI16_shortcut)	C++14	0 / 100	1 ms	204 KiB

shortcut

#include "shortcut.h"
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<ll,ll> pii;
typedef vector<pii> vii;
typedef vector<vii> vvii;

const ll INF=100000000000000000;

void dfs(ll n,vvii &conex, ll v, ll &mej){
    vector<bool> porvisitar(2*n,true);
    priority_queue<pii> cola;
    cola.push(pii{0,v});
    while (cola.size()){
        pii x=cola.top();
        cola.pop();
        if (porvisitar[x.second]){
            porvisitar[x.second]=false;
            mej=max(mej,-x.first);
            for (pii y:conex[x.second]){
                if (porvisitar[y.second]) cola.push(pii{x.first-y.first,y.second});
            }
        }
    }
}

ll distance_l(int i, int j, vi &len, int lenciclo, vi &prof){
    return(max(abs(len[i]-len[j]),lenciclo-abs(len[i]-len[j])))+prof[i]+prof[j];
}

ll find_shortcut(int n, vi l, vi d, int c)
{
    vvii conexiones(2*n);
    for (int i=0;i<n-1;i++){
        conexiones[i].push_back(pii{l[i],i+1});
        conexiones[i+1].push_back(pii{l[i],i});
    }
    for (int i=0;i<n;i++){
        conexiones[i].push_back(pii{d[i],i+n});
        conexiones[n+i].push_back(pii{d[i],i});
    }
    ll mejor=INF;
    for (int i=0;i<n;i++){
        for (int j=i+1;j<n;j++){
            vvii conex=conexiones;
            conex[i].push_back(pii{c,j});
            conex[j].push_back(pii{c,i});
            ll mej=0;
            dfs(n,conex,n,mej);
            dfs(n,conex,2*n-1,mej);
            //ciclo
                {vi lon(j-i+1);
                vi prof(j-i);
                for (int a=0;a<j-i;a++) lon[a]=l[i+a];
                for (int a=0;a<j-i;a++) prof[a]=d[i+a];
                lon[j-i]=c;
                vi len_l(j-i+1);
                len_l[0]=0;
                for (int a=1;a<j-i+1;a++) len_l[a]=len_l[a-1]+lon[a-1];
                //vi len_r(j-1+1);
                //for (int a=0;a<j-i+1;a++) len_r[a]=len_l[j-i]+c-len_l[a];
                int ac=1;
                for (int a=0;a<j-i+1;a++){
                    //while (min(len_l[ans]-len_l[a]+ lon[ans]+lon[a] ,len_l[ans]+len_l[j-i]-len_l[a]+c- lon[ans]+lon[a] )< min(len_l[(ans+1)%n]-len_l[a]+ lon[(ans+1)%n]+lon[a] ,len_l[(ans+1)%n]+len_l[j-i]-len_l[a]+c- lon[ans]+lon[a] ))
                    while (distance_l(a,ac,len_l,len_l[j-i]+c,prof)<distance_l(a,(ac+1)%(j-i+1),len_l,len_l[j-i]+c,prof)) ac=(ac+1)%(j-i+1);
                    mej=max(mej,distance_l(a,ac,len_l,len_l[j-i]+c,prof));
                }
                }

            mejor=min(mejor,mej);
        }
    }
    return mejor;
}

• 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