Submission #606560

#	Time	Username	Problem	Language	Result	Execution time	Memory
606560		rrrr10000	Sky Walking (IOI19_walk)	C++14	100 / 100	1515 ms	264060 KiB

walk

#include "walk.h"

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef pair<ll,ll> P;
typedef tuple<ll,ll,ll> PP;
typedef vector<P> vp;
typedef vector<vp> vvp;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define REP(i,k,n) for(ll i=(ll)(k);i<(ll)(n);i++)
#define pb emplace_back
#define all(a) a.begin(),a.end()
#define dupli(a) {sort(all(a));a.erase(unique(all(a)),a.end());}
#define SPQ(a) priority_queue<a,vector<a>,greater<a>>
#define fi first
#define se second
#define rsort(a) {sort(all(a));reverse(all(a));}
template<class T> bool chmin(T&a,T b){if(a>b){a=b;return true;}return false;}
template<class T> void outvp(T v){rep(i,v.size()){cout<<'('<<v[i].fi<<','<<v[i].se<<')';}cout<<endl;}
const ll inf=1001001001001001001;
ll dijkstra(ll n,vector<PP> edge,ll from,ll to){
	vvp g(n);
	for(auto x:edge){
		ll a,b,c;tie(a,b,c)=x;
		g[a].pb(b,c);g[b].pb(a,c);
	}
	SPQ(P) pq;pq.emplace(0,from);
	vi dis(n,inf);dis[from]=0;
	while(!pq.empty()){
		auto t=pq.top();pq.pop();
		if(dis[t.se]!=t.fi)continue;
		for(auto x:g[t.se])if(chmin(dis[x.fi],t.fi+x.se))pq.emplace(dis[x.fi],x.fi);
	}
	if(dis[to]==inf)return -1;
	return dis[to];
}
long long min_distance(std::vector<int> X, std::vector<int> h, std::vector<int> l, std::vector<int> r, std::vector<int> y, int from, int to) {
	ll n=X.size(),m=l.size();
	set<P> S;
	vvi L(n),R(n);
	rep(i,m)L[l[i]].pb(i);
	rep(i,m)R[r[i]].pb(i);
	ll cnt=0,F,T;
	vvp yoko(m);
	vector<PP> edge;
	vvp sp2(n);
	vp srt(m);
	rep(i,m)srt[i]=P(y[i],i);
	rsort(srt);
	set<ll> S2;
	priority_queue<P> pq;
	rep(i,n)pq.emplace(h[i],i);
	for(auto x:srt){
		while(pq.size()&&pq.top().fi>=x.fi){
			S2.insert(pq.top().se);pq.pop();
		}
		auto itr=S2.lower_bound(from);
		if(itr!=S2.begin())itr--;
		rep(t,3){
			if(itr==S2.end())break;
			if(l[x.se]<=*itr&&*itr<=r[x.se])sp2[*itr].pb(x);
			itr++;
		}
		itr=S2.lower_bound(to);
		if(itr!=S2.begin())itr--;
		rep(t,3){
			if(itr==S2.end())break;
			if(l[x.se]<=*itr&&*itr<=r[x.se])sp2[*itr].pb(x);
			itr++;
		}
	}
	rep(i,n){
		vp sp;
		for(ll t:L[i])S.insert(P(y[t],t));
		for(ll t:L[i]){
			sp.pb(y[t],t);
			auto itr=S.lower_bound(P(y[t],t));
			if(itr!=S.begin()){
				itr--;sp.pb(*itr);
			}
		}
		for(ll t:R[i]){
			sp.pb(y[t],t);
			auto itr=S.lower_bound(P(y[t],t));
			if(itr!=S.begin()){
				itr--;sp.pb(*itr);
			}
		}
		if(S.size())sp.pb(*S.begin());
		sp.pb(0,-1);
		for(auto x:sp2[i])sp.pb(x);
		for(ll t:R[i])S.erase(P(y[t],t));
		dupli(sp);
		while(sp.size()&&sp.back().fi>h[i])sp.pop_back();
		rep(j,sp.size()-1){
			edge.pb(cnt+j,cnt+j+1,sp[j+1].fi-sp[j].fi);
		}
		REP(j,1,sp.size())yoko[sp[j].se].pb(i,cnt+j);
		if(from==i)F=cnt;
		if(to==i)T=cnt;
		cnt+=sp.size();
	}
	rep(i,m)rep(j,yoko[i].size()-1)edge.pb(yoko[i][j].se,yoko[i][j+1].se,X[yoko[i][j+1].fi]-X[yoko[i][j].fi]);
	return dijkstra(cnt,edge,F,T);
}

Compilation message (stderr)

walk.cpp: In function 'long long int min_distance(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, int, int)':
walk.cpp:107:17: warning: 'T' may be used uninitialized in this function [-Wmaybe-uninitialized]
  107 |  return dijkstra(cnt,edge,F,T);
      |         ~~~~~~~~^~~~~~~~~~~~~~
walk.cpp:107:17: warning: 'F' may be used uninitialized in this function [-Wmaybe-uninitialized]

• Subtask 1: 10 / 10
• Subtask 2: 14 / 14
• Subtask 3: 15 / 15
• Subtask 4: 18 / 18
• Subtask 5: 43 / 43