Submission #1232367

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

shortcut

#include <bits/stdc++.h>
#define ll long long
#define dbg(x) cerr << #x << ' ' << x << endl;
#define inf (ll) 1e17
using namespace std;
vector<vector<pair<ll,ll>>> adj;
long long find_shortcut(int n, std::vector<int> l, std::vector<int> d, int c)
{
    ll ans=inf;
    adj.resize(2*n);
    for (int i=1;i<n;i++)
    {
        adj[i].push_back({i-1,l[i-1]});
        adj[i-1].push_back({i,l[i-1]});
    }
    for (int i=0;i<n;i++)
    {
        if(d[i])
        {
            adj[i+n].push_back({i,d[i]});
            adj[i].push_back({i+n,d[i]});
        }
    }
    for (int i=0;i<n-1;i++)
    {
        for (int j=i+1;j<n;j++)
        {
            vector<vector<pair<ll,ll>>> g=adj;
            if(j-i!=0)
            {
                g[i].push_back({j,c});
                g[j].push_back({i,c});
            }
            ll d=0;
            for (int i=0;i<2*n;i++)
            {
                vector<ll> dist(2*n,inf);
                dist[i]=0;
                priority_queue<pair<ll,ll>,vector<pair<ll,ll>>,greater<pair<ll,ll>>> pq;
                pq.push({0,i});
                while(!pq.empty())
                {
                    ll node=pq.top().second;
                    pq.pop();
                    for (auto &&e : g[node])
                    {
                        if(dist[e.first] > dist[node]+e.second)
                        {
                            dist[e.first]=dist[node]+e.second;
                            pq.push({dist[e.first],e.first});
                        }
                    }
                }   
                for (int i=0;i<2*n;i++)
                {
                    if(dist[i]!=inf)
                    {
                        d=max(d,dist[i]);
                    }
                }
            }
            ans=min(ans,d);
        }
    }
    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