Submission #1175673

#	Time	Username	Problem	Language	Result	Execution time	Memory
1175673		Warinchai	Relay Marathon (NOI20_relaymarathon)	C++20	25 / 100	1860 ms	103924 KiB

RelayMarathon

#include<bits/stdc++.h>
using namespace std;

int n,m,k;
int X=4;

vector<pair<int,int>>adj[100005];
vector<pair<int,int>>dis[100005];
map<int,int>has[100005];
vector<int>sp;
struct state{
    int root,dis,cur;
    state(int r,int d,int c){
        root=r,dis=d,cur=c;
    }
    friend bool operator<(state a,state b){
        return a.dis>b.dis;
    }
};
int inf=1e9;
priority_queue<state>pq;
int can(pair<int,pair<int,int>>ans1,pair<int,pair<int,int>>ans2){
    if(ans1.first==inf||ans2.first==inf)return -inf;
    if(ans1.second.first==ans2.second.first||ans1.second.first==ans2.second.second)return -ans1.second.first;
    if(ans1.second.second==ans2.second.first||ans1.second.second==ans2.second.second)return -ans1.second.second;
    return ans1.first+ans2.first;
}
map<pair<int,int>,int>mp;

vector<pair<int,pair<int,int>>>closest_pair(vector<int>s,int sz){
    for(auto x:s){
        pq.push(state(x,0,x));
        dis[x][0]={0,x};
    }
    while(!pq.empty()){
        int d=pq.top().dis;
        int u=pq.top().cur;
        int r=pq.top().root;
        pq.pop();

        for(auto v:adj[u]){
            int x=v.first;

            if(d+v.second>=dis[x][X-1].first)continue;

            int temp=-1;
            for(int i=0;i<X;i++)if(dis[x][i].second==r)temp=i;
            if(temp!=-1)continue;

            dis[x].push_back({d+v.second,r});
            sort(dis[x].begin(),dis[x].end());
            temp=dis[x][X].second;
            dis[x].pop_back();
            if(temp==r)continue;
            pq.push({state(r,d+v.second,v.first)});
        }
    }
    pair<int,pair<int,int>>ans[X];
    for(int i=0;i<4;i++){
        ans[i]={inf,{inf,inf}};
    }
    for(int i=1;i<=n;i++){
        for(int j=0;j<X;j++){
            for(int k=j+1;k<X;k++){
                if(dis[i][j].first==inf||dis[i][k].first==inf)continue;
                int val=dis[i][j].first+dis[i][k].first;
                int x=dis[i][j].second;
                int y=dis[i][k].second;
                if(x>y)swap(x,y);
                if(mp[{x,y}]==0||mp[{x,y}]>val)mp[{x,y}]=val;
            }
        }
    }
    for(auto x:mp){
        int val=x.second;
        int u=x.first.first;
        int v=x.first.second;
        if(val<ans[0].first){
            ans[3]=ans[2];
            ans[2]=ans[1];
            ans[1]=ans[0];
            ans[0]={val,{u,v}};
        }else if(val<ans[1].first){
            ans[3]=ans[2];
            ans[2]=ans[1];
            ans[1]={val,{u,v}};
        }else if(val<ans[2].first){
            ans[3]=ans[2];
            ans[2]={val,{u,v}};
        }else if(val<ans[3].first){
            ans[3]={val,{u,v}};
        }
    }
    //cerr<<ans[0].second.second<<" "<<ans[1].second.second<<"\n";
    vector<pair<int,pair<int,int>>>pairs;
    for(int i=0;i<X;i++)pairs.push_back(ans[i]);
    for(auto x:s);
    return pairs;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++)dis[i].resize(X,{inf,inf});
    for(int i=0;i<m;i++){
        int u,v,w;cin>>u>>v>>w;
        adj[u].push_back({v,w});
        adj[v].push_back({u,w});
    }
    for(int i=1;i<=k;i++){
        int x;cin>>x;
        sp.push_back(x);
    }

    int ans=inf;

    vector<pair<int,pair<int,int>>>rans;

    auto v=closest_pair(sp,2);
    //for(auto x:v)cerr<<x.first<<" "<<x.second.first<<" "<<x.second.second<<"\n";
    //cerr<<"\n";
    int temp=can(v[0],v[1]);
    rans.push_back(v[0]);
    rans.push_back(v[1]);
    if(temp>0){
        cout<<temp;
        return 0;
    }
    int xx=temp*-1;

    vector<int>nsp;
    for(auto v:sp)if(v!=xx)nsp.push_back(v);
    v=closest_pair(nsp,1);
    rans.push_back(v[0]);
    temp=can(v[0],rans[1]);
    if(temp>0)ans=min(ans,temp);
    temp=can(v[0],rans[0]);
    if(temp>0){
        cout<<temp;
        return 0;
    }
    int y=temp*-1;

    nsp.clear();
    for(auto v:sp)if(v!=xx&&v!=y)nsp.push_back(v);
    v=closest_pair(nsp,1);
    rans.push_back(v[0]);
    temp=can(v[0],rans[0]);
    if(temp>0)ans=min(ans,temp);

    /*for(auto x:rans){
        cerr<<x.first<<" "<<x.second.first<<" "<<x.second.second<<"\n";
    }*/
    assert(xx>0&&y>0);    
    cout<<ans;
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 12
• Subtask 3: 25 / 25
• Subtask 4: 0 / 58