Submission #573954

#	Time	Username	Problem	Language	Result	Execution time	Memory
573954		PedroBigMan	Sky Walking (IOI19_walk)	C++14	24 / 100	4088 ms	705312 KiB

walk

/*
Author of all code: Pedro BIGMAN Dias
Last edit: 15/02/2021
*/
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#pragma GCC optimize("Ofast")
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <string>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <queue>
#include <deque>
#include <list>
#include <iomanip>
#include <stdlib.h>
#include <time.h>
#include <cstring>
#include "walk.h"
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;
typedef long double ld;
#define REP(i,a,b) for(ll i=(ll) a; i<(ll) b; i++)
#define pb push_back
#define mp make_pair
#define pl pair<ll,ll>
#define ff first
#define ss second
#define whole(x) x.begin(),x.end()
#define DEBUG(i) cout<<"Pedro Is The Master "<<i<<endl
#define INF 10000000000000000LL
#define EPS ((ld)0.00000000001)
#define pi ((ld)3.141592653589793)
#define VV(vvvv,NNNN,xxxx); REP(iiiii,0,NNNN) {vvvv.pb(xxxx);}
ll mod=1000000007LL;

template<class A=ll> 
void Out(vector<A> a) {REP(i,0,a.size()) {cout<<a[i]<<" ";} cout<<endl;}

template<class A=ll>
void In(vector<A> &a, ll N) {A cur; REP(i,0,N) {cin>>cur; a.pb(cur);}} 

class WG //everything works for weighted directed graphs except dynamic graph
{
    public:
    ll N; vector<vector<pl> > adj;
    vector<bool> pr; 
    
    WG(vector<vector<pl> > ad)
    {
        adj=ad; N=adj.size();
        REP(i,0,N) {pr.pb(false);}
    }
    
    vector<ll> Dijkstra(ll s)
    {
        vector<ll> d; REP(i,0,N) {d.pb(INF);}
        d[s]=0;
        priority_queue<pl> q;
        q.push(mp(0,s));
        ll cur;
        while(!q.empty())
        {
            cur=q.top().ss; q.pop();
            if(pr[cur]) {continue;}
            pr[cur]=true; 
            REP(i,0,adj[cur].size())
            {
                if(d[adj[cur][i].ff]>d[cur]+adj[cur][i].ss)
                {
                    d[adj[cur][i].ff]=d[cur]+adj[cur][i].ss;
                    q.push(mp(-d[adj[cur][i].ff],adj[cur][i].ff));
                }
            }
        }
        return d;
	}
};

ll min_distance(vector<int> x, vector<int> h, vector<int> l, vector<int> r, vector<int> y, int s, int g) 
{
	ll N = x.size(); ll M = l.size();
	vector<vector<ll> > be,en; VV(be,N,{}); VV(en,N,{});
	REP(i,0,M) {be[l[i]].pb(i); en[r[i]].pb(i);}
	multiset<ll> active; multiset<ll>::iterator it; active.insert(0);
	vector<pl> p; 
	vector<vector<ll> > inter; 
	vector<ll> fir;
	REP(i,0,N)
	{
		fir.pb(p.size());
		REP(j,0,be[i].size()) 
		{
			active.insert(y[be[i][j]]);
		}
		it=active.begin(); 
		while(it!=active.end() && *it <= h[i])
		{
			p.pb({x[i],*it});
			it++;
		}
		REP(j,0,en[i].size()) 
		{
			active.erase(active.find(y[en[i][j]]));
		}
	}
	ll P = p.size(); vector<vector<pl> > adj; VV(adj,P,{}); ll we;
	REP(i,0,P-1)
	{
		if(p[i+1].ff==p[i].ff) {we=p[i+1].ss-p[i].ss; adj[i].pb({i+1,we}); adj[i+1].pb({i,we});}
	}
	map<ll,vector<ll> > m;
	REP(i,0,P) 
	{
		if(m.find(p[i].ss)==m.end()) {m[p[i].ss]={};}
		m[p[i].ss].pb(i);
	}
	map<ll,vector<ll> >::iterator it2; ll ind1,ind2;
	REP(i,0,M)
	{
		ll j = (ll) (lower_bound(whole(m[y[i]]),fir[l[i]]) - m[y[i]].begin());
		it2=m.find(y[i]);
		while(1>0)
		{
			ind1=it2->ss[j]; ind2=it2->ss[j+1]; we=p[ind2].ff-p[ind1].ff;
			adj[ind1].pb({ind2,we}); adj[ind2].pb({ind1,we});
			if(p[ind2].ff==x[r[i]]) {break;}
			j++;
		}
	}
	
	ll A = (ll) (find(whole(p),(pl){x[s],0}) - p.begin());
	ll B = (ll) (find(whole(p),(pl){x[g],0}) - p.begin());
	//REP(i,0,P) {cout<<i<<" "<<p[i].ff<<" "<<p[i].ss<<endl;}
	//REP(i,0,P) {cout<<i<<endl;REP(j,0,adj[i].size()) {cout<<adj[i][j].ff<<" "<<adj[i][j].ss<<endl;}} 
	WG G(adj);
	vector<ll> d = G.Dijkstra(A); 
	if(d[B]>=INF) {return -1;}
	//REP(i,0,P) {cout<<p[i].ff<<" "<<p[i].ss<<" "<<d[i]<<endl;}
	return d[B];
}

Compilation message (stderr)

walk.cpp:5: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    5 | #pragma GCC optimization ("O3")
      | 
walk.cpp:6: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    6 | #pragma GCC optimization ("unroll-loops")
      |

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