Submission #1180707

#	Time	Username	Problem	Language	Result	Execution time	Memory
1180707		8pete8	Relay Marathon (NOI20_relaymarathon)	C++20	100 / 100	2899 ms	298020 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{
	int v[mxn+10];
	vector<int>keep;
	void init(){
		keep.clear();
		for(int i=0;i<=2*n;i++)v[i]=inf;
	}
	
	void update(int pos,int val){
		pos+=n;
		keep.pb(pos);
		v[pos]=min(v[pos],val);
		for(int i=pos;i>0;i>>=1)v[i>>1]=min(v[i],v[i^1]);
	}
	int qry(int l,int r){
		int ans=inf;
		for(l+=n,r+=n;l<=r;l>>=1,r>>=1){
			if(l&1)ans=min(ans,v[l++]);
			if(!(r&1))ans=min(ans,v[r--]);
		}
		return ans;
	}
	void re(){
		for(auto pos:keep){
			v[pos]=inf;
			for(int i=pos;i>0;i>>=1)v[i>>1]=min(v[i],v[i^1]);
		}
		keep.clear();
	}
}t;
int ans=inf;
vector<pii>event[mxn+10];
struct rec{
	int LX,RX,LY,RY,val;
};
bool cmpF(rec a,rec b){
	return a.LY>b.LY;
}
bool cmpS(rec a,rec b){
	return a.RY<b.RY;
}
void dnc(int l,int r,vector<rec>Q){
	int mid=l+(r-l)/2;
	vector<rec>L,R;
	sort(all(Q),cmpF);
	int cur=mid;
	for(auto i:Q){
		if(i.LY<=mid&&i.RY>mid){
			while(i.LY<=cur){
				for(auto j:event[cur])t.update(j.f,j.s);
				cur--;
			}
			ans=min(ans,i.val+t.qry(i.LX,i.RX));
		}
		else if(i.RY<=mid)L.pb(i);
		else R.pb(i);
	}
	t.re();

	sort(all(Q),cmpS);
	cur=mid+1;
	for(auto i:Q){
		if(i.LY<=mid&&i.RY>mid){
			while(i.RY>=cur){
				for(auto j:event[cur])t.update(j.f,j.s);
				cur++;
			}
			ans=min(ans,i.val+t.qry(i.LX,i.RX));
		}
	}
	t.re();
	if(l==r)return;

	dnc(l,mid,L);
	dnc(mid+1,r,R);
}
bool cmp(pair<int,pii> a,pair<int,pii> b){return a.s.f<b.s.f;}
bool cmp2(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.f,i.s.s);
	for(auto i:have)event[i.s.s].pb({i.s.f,i.f});

	int cur=1;
	
	sort(all(have),cmp);
	t.init();
	for(int i=0;i<have.size();i++){
		vector<pii>upd;
		while(cur<=n&&cur<have[i].s.f){
			for(auto j:event[cur])t.update(j.f,j.s);
			cur++;
		}
		ans=min(ans,have[i].f+t.qry(1,have[i].s.f-1));
		ans=min(ans,have[i].f+t.qry(have[i].s.f+1,have[i].s.s-1));
		ans=min(ans,have[i].f+t.qry(have[i].s.s+1,n));
	}
	t.init();

	cur=n;
	sort(all(have),cmp2);
	for(int i=0;i<have.size();i++){
		while(cur>=1&&cur>have[i].s.s){
			for(auto j:event[cur])t.update(j.f,j.s);
			cur--;
		}
		ans=min(ans,have[i].f+t.qry(1,have[i].s.f-1));
		ans=min(ans,have[i].f+t.qry(have[i].s.f+1,have[i].s.s-1));
		ans=min(ans,have[i].f+t.qry(have[i].s.s+1,n));
	}
	t.init();

	vector<rec>ask;
	for(auto i:have){
		ask.pb((rec){1,i.s.f-1,i.s.s+1,i.s.f-1,i.f});
		ask.pb((rec){i.s.f+1,i.s.s-1,i.s.s+1,i.s.f-1,i.f});
		ask.pb((rec){i.s.s+1,n,i.s.s+1,i.s.f-1,i.f});
	}
	dnc(1,n,ask);
	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:55:19: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   55 |         void init(){
      |                   ^
RelayMarathon.cpp:60:36: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   60 |         void update(int pos,int val){
      |                                    ^
RelayMarathon.cpp:66:28: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   66 |         int qry(int l,int r){
      |                            ^
RelayMarathon.cpp:74:17: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   74 |         void re(){
      |                 ^
RelayMarathon.cpp:87:22: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   87 | bool cmpF(rec a,rec b){
      |                      ^
RelayMarathon.cpp:90:22: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   90 | bool cmpS(rec a,rec b){
      |                      ^
RelayMarathon.cpp:93:34: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   93 | void dnc(int l,int r,vector<rec>Q){
      |                                  ^
RelayMarathon.cpp:128:41: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
  128 | bool cmp(pair<int,pii> a,pair<int,pii> b){return a.s.f<b.s.f;}
      |                                         ^
RelayMarathon.cpp:129:42: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
  129 | bool cmp2(pair<int,pii> a,pair<int,pii> b){return a.s.s>b.s.s;}
      |                                          ^
RelayMarathon.cpp:130:14: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
  130 | 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: 25 / 25
• Subtask 4: 58 / 58