Submission #1264205

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

shortcut

#pragma once
#include <bits/stdc++.h>

using namespace std;

const long long INF=1e18;

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,int>>> adj(ntodos+1);
    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<(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=0;j<nn;j++){
            if(i==j)continue;
            auto adj2=adj;
            adj2[i].push_back({j, c});
            adj2[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:adj2[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;
            };
            auto fur=dijkstra(0);
            auto fur2=dijkstra(fur.second);
            ans=min(ans, fur2.first);
        }
    }
    return ans;
}

Compilation message (stderr)

shortcut.cpp:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~
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