Submission #1180639

#	Time	Username	Problem	Language	Result	Execution time	Memory
1180639		8pete8	Relay Marathon (NOI20_relaymarathon)	C++20	17 / 100	6092 ms	92080 KiB

RelayMarathon

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define f first
#define s second
#define pii pair<int32_t,int32_t>
#define ppii pair<int,pii>
#define vi vector<int>
#define pb push_back
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define F(n) for(int i=0;i<n;i++)
#define lb lower_bound
#define ub upper_bound
#define fastio ios::sync_with_stdio(false);cin.tie(NULL);
#pragma GCC optimize ("03,unroll-lopps")
#define sz(x) (int)((x).size())
#define int long long
using namespace std;
const int mod=1e9+7,mxn=2e5,inf=1e9,minf=-1e9,lg=30,Mxn=1e9;
//#undef int
int n,k,m,d,q;
void setIO(string name){
	ios_base::sync_with_stdio(0); cin.tie(0);
	freopen((name+".in").c_str(),"r",stdin);
	freopen((name+".out").c_str(),"w",stdout);
}
vector<pii>dist[mxn+10];
vector<pii>adj[mxn+10];
int have(int x,pii a){
	for(auto i:dist[x])if(i==a)return 1;
	return 0;
}
bool put(int x,pii a){
	for(auto &i:dist[x])if(i.s==a.s){
		if(i.f>a.f)return i.f=a.f,1;
		return 0;
	}
	if(dist[x].size()<3)return dist[x].pb(a),1;
	sort(all(dist[x]));
	if(a.f<dist[x].back().f){
		dist[x].pop_back();
		dist[x].pb(a);
		return 1;
	}
	return 0;
}
bool good(pii a,pii b){
	if(a.f==b.f||a.f==b.s||a.s==b.f||a.s==b.s)return 0;
	return 1;
}
int32_t main(){
	fastio
	cin>>n>>m>>k;
	for(int i=0;i<m;i++){
		int a,b,c;cin>>a>>b>>c;
		adj[a].pb({b,c});
		adj[b].pb({a,c});
	}
	vector<int>SP(k);
	priority_queue<pair<int,pii>,vector<pair<int,pii>>,greater<pair<int,pii>>>pq;
	for(auto &i:SP){
		cin>>i;
		pq.push({0,{i,i}});
	}
	while(!pq.empty()){
		int C=pq.top().f,cur=pq.top().s.f,F=pq.top().s.s;
		pq.pop();
		if(cur!=F&&!have(cur,{C,F}))continue;
		for(auto i:adj[cur]){
			if(i.f!=F&&put(i.f,{C+i.s,F}))pq.push({C+i.s,{i.f,F}});
		}
	}
	vector<pair<int,pii>>have;
	for(auto i:SP){
		for(auto j:dist[i])have.pb({j.f,{i,j.s}});
	}
	int ans=inf;
	sort(all(have));
	//brute check?
	for(int i=0;i<have.size();i++)for(int j=i+1;j<have.size();j++){
		if(good(have[i].s,have[j].s))ans=min(ans,have[i].f+have[j].f);
	}
	cout<<ans;
}
/*

*/

Compilation message (stderr)

RelayMarathon.cpp:16:40: warning: bad option '-funroll-lopps' to pragma 'optimize' [-Wpragmas]
   16 | #pragma GCC optimize ("03,unroll-lopps")
      |                                        ^
RelayMarathon.cpp:23:23: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   23 | void setIO(string name){
      |                       ^
RelayMarathon.cpp:30:21: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   30 | int have(int x,pii a){
      |                     ^
RelayMarathon.cpp:34:21: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   34 | bool put(int x,pii a){
      |                     ^
RelayMarathon.cpp:48:22: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   48 | bool good(pii a,pii b){
      |                      ^
RelayMarathon.cpp:52:14: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   52 | int32_t main(){
      |              ^
RelayMarathon.cpp: In function 'void setIO(std::string)':
RelayMarathon.cpp:25:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   25 |         freopen((name+".in").c_str(),"r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
RelayMarathon.cpp:26:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   26 |         freopen((name+".out").c_str(),"w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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