Submission #1211891

#	Time	Username	Problem	Language	Result	Execution time	Memory
1211891		Marco_Escandon	Shortcut (IOI16_shortcut)	C++20	0 / 100	0 ms	328 KiB

shortcut

//#include "shortcut.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<vector<pair<int,ll>>> cad;
ll a, b, c;
pair<ll,ll> asd(int d)
{
    cad[a].push_back({b,c});
    cad[b].push_back({a,c});
    priority_queue<pair<ll,ll>> q;
    vector<ll> v(cad.size()+1,-1);
    q.push({0,d});
    pair<ll,ll> asd={0,0};
    while(!q.empty())
    {
        pair<ll,ll> temp=q.top();q.pop();
        if(v[temp.second]==-1)
        {
            v[temp.second]=-temp.first;
            asd=max(asd,{v[temp.second],temp.second});
            for(auto i:cad[temp.second])
            {
                if(v[i.first]==-1)
                    q.push({temp.first-i.second,i.first});
            }
        }
    }
    cad[a].pop_back();
    cad[b].pop_back();
    return asd;
}
long long find_shortcut(int n, vector<int> l, vector<int> d, int C)
{
    cad.resize(2*n+5);
    for(int i=0; i<n-1; i++)
    {
        cad[i].push_back({i+1,l[i]});
        cad[i+1].push_back({i,l[i]});
        cad[i].push_back({n+i,d[i]});
        cad[n+i].push_back({i,d[i]});
    }
    cad[n-1].push_back({n-1+n,d[n-1]});
    cad[n-1+n].push_back({n-1,d[n-1]});
    ll ans=1e17;
    c=C;
    for(int i=0; i<n; i++)
    {
        for(int j=i+1; j<n; j++)
        {
            a=i;b=j;
            pair<ll,ll> temp=asd(0);
            pair<ll,ll> t1=asd(temp.second);
            temp=max(temp,t1);
            t1=asd(n-1);
            temp=max(temp,asd(t1.second));
            ans=min(ans,temp.first);
        }
    }
    return ans;
}

Compilation message (stderr)

shortcut.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~
shortcut_c.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~

• 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