Submission #1180658

#	Time	Username	Problem	Language	Result	Execution time	Memory
1180658		8pete8	Relay Marathon (NOI20_relaymarathon)	C++20	0 / 100	6069 ms	475568 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;
}
struct seg{
	vector<int>val,L,R;
	int create(){
		val.pb(inf);
		L.pb(0);
		R.pb(0);
		return L.size()-1;
	}
	seg(){
		for(int i=0;i<2;i++)create();
	}
	void update(int qpos,int x,int pos,int l,int r){
		if(l>qpos||r<qpos)return;
		if(l==r)return void(val[pos]=min(val[pos],x));
		int mid=(l+r)>>1;
		if(qpos<=mid){
			if(!L[pos])L[pos]=create();
			update(qpos,x,L[pos],l,mid);
		}
		else{
			if(!R[pos])R[pos]=create();
			update(qpos,x,R[pos],mid+1,r);
		}
		val[pos]=min(val[L[pos]],val[R[pos]]);
	}
	int qry(int ql,int qr,int pos,int l,int r){
		if(l>qr||r<ql||pos==0)return inf;
		if(ql<=l&&r<=qr)return val[pos];
		int mid=(l+r)>>1;
		return min(qry(ql,qr,L[pos],l,mid),qry(ql,qr,R[pos],mid+1,r));
	}
};
vector<int>L,R;
vector<seg>t;
int create(){
	L.pb(0);
	R.pb(0);
	t.pb(seg());
	return L.size()-1;
}
void update(int qx,int qy,int x,int pos=1,int l=1,int r=n){
	if(l>qx||r<qx)return;
	if(l==r)return;
	t[pos].update(qy,x,1,1,n);
	int mid=(l+r)>>1;
	if(qx<=mid){
		if(!L[pos])L[pos]=create();
		update(qx,qy,x,L[pos],l,mid);
	}
	else{
		if(!R[pos])R[pos]=create();
		update(qx,qy,x,R[pos],mid+1,r);
	}
}
int qry(int LX,int RX,int LY,int RY,int pos=1,int l=1,int r=n){
	if(l>RX||r<LX||pos==0)return inf;
	if(LX<=l&&r<=RX)return t[pos].qry(LY,RY,1,1,n);
	int mid=(l+r)>>1;
	return min(qry(LX,RX,LY,RY,L[pos],l,mid),qry(LX,RX,LY,RY,R[pos],mid+1,r));
}
bool cmp(pair<int,pii> a,pair<int,pii> b){return a.s.s<b.s.s;}
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}});
	}
	for(auto &i:have)if(i.s.f>i.s.s)swap(i.s.s,i.s.f);
	ll ans=inf;
	create();
	create();
	sort(all(have),cmp);
	for(auto i:have)update(i.s.f,i.s.s,i.f);
	for(auto i:have){
		ans=min(ans,(ll)i.f+(ll)qry(1,i.s.f-1,1,i.s.f-1));
		ans=min(ans,(ll)i.f+(ll)qry(i.s.s+1,i.s.f-1,1,i.s.f-1));
		ans=min(ans,(ll)i.f+(ll)qry(i.s.f+1,n,1,i.s.f-1));

		ans=min(ans,(ll)i.f+(ll)qry(1,i.s.f-1,i.s.f+1,i.s.s-1));
		ans=min(ans,(ll)i.f+(ll)qry(i.s.s+1,i.s.f-1,i.s.f+1,i.s.s-1));
		ans=min(ans,(ll)i.f+(ll)qry(i.s.f+1,n,i.s.f+1,i.s.s-1));

		ans=min(ans,(ll)i.f+(ll)qry(1,i.s.f-1,i.s.s+1,n));
		ans=min(ans,(ll)i.f+(ll)qry(i.s.s+1,i.s.f-1,i.s.s+1,n));
		ans=min(ans,(ll)i.f+(ll)qry(i.s.f+1,n,i.s.s+1,n));

	}
	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:54:20: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   54 |         int create(){
      |                    ^
RelayMarathon.cpp:60:13: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   60 |         seg(){
      |             ^
RelayMarathon.cpp:63:55: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   63 |         void update(int qpos,int x,int pos,int l,int r){
      |                                                       ^
RelayMarathon.cpp:77:50: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   77 |         int qry(int ql,int qr,int pos,int l,int r){
      |                                                  ^
RelayMarathon.cpp:86:12: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   86 | int create(){
      |            ^
RelayMarathon.cpp:92:58: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   92 | void update(int qx,int qy,int x,int pos=1,int l=1,int r=n){
      |                                                          ^
RelayMarathon.cpp:106:62: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
  106 | int qry(int LX,int RX,int LY,int RY,int pos=1,int l=1,int r=n){
      |                                                              ^
RelayMarathon.cpp:112:41: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
  112 | bool cmp(pair<int,pii> a,pair<int,pii> b){return a.s.s<b.s.s;}
      |                                         ^
RelayMarathon.cpp:113:14: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
  113 | 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: 0 / 5
• Subtask 2: 0 / 12
• Subtask 3: 0 / 25
• Subtask 4: 0 / 58