Submission #1264208

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

shortcut

#include <bits/stdc++.h>

using namespace std;

const long long INF=LLONG_MAX;

long long find_shortcut(int n, std::vector <int> l, std::vector <int> d, int c){
    int cnt=0, nxt=0;
    for(int i=0;i<(int)d.size();i++){
        if(d[i])cnt++;
    }
    int ntodos=l.size()+1+cnt;
    vector<vector<pair<int,long long>>> adj(ntodos+1);
    for(int i=0;i<(int)l.size();i++){
        adj[i].push_back({i+1, l[i]});
        adj[i+1].push_back({i, l[i]});
    }
    for(int i=0;i<(int)d.size();i++){
        if(d[i]){
            adj[i].push_back({l.size()+nxt+1, d[i]});
            adj[l.size()+nxt+1].push_back({i, d[i]});
            nxt++;
        }
    }
    int nn=l.size()+1;
    long long ans=INF;
    for(int i=0;i<nn;i++){
        for(int j=i+1;j<nn;j++){
            if(i==j)continue;
            adj[i].push_back({j, c});
            adj[j].push_back({i, c});
            auto dijkstra=[&](int start){
                set<pair<long long,int>> s;
                s.insert({0,start});
                vector<long long> dist(ntodos, INF);
                dist[start]=0;
                while(!s.empty()){
                    int u=s.begin()->second;
                    s.erase(s.begin());
                    for(auto v:adj[u]){
                        if(dist[v.first]>dist[u]+v.second){
                            dist[v.first]=dist[u]+v.second;
                            s.insert({dist[v.first],v.first});
                        }
                    }
                }
                pair<long long, int> maxi={0,0};
                for(int i=0;i<ntodos;i++)maxi=max(maxi,{dist[i],i});
                return maxi;
            };
            long long dia=0;
            for(int s=0;s<ntodos;s++){
                auto fur=dijkstra(s);
                dia=max(dia, fur.first);
            }
            ans=min(ans, dia);
            adj[i].pop_back();
            adj[j].pop_back();
        }
    }
    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