/*
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 1000000000000000000LL
#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);
//REP(i,0,P) {cout<<p[i].ff<<" "<<p[i].ss<<" "<<d[i]<<endl;}
return d[B];
}
Compilation message
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")
|
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
340 KB |
Output is correct |
| 4 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1215 ms |
250920 KB |
Output is correct |
| 4 |
Correct |
1267 ms |
272272 KB |
Output is correct |
| 5 |
Correct |
872 ms |
234964 KB |
Output is correct |
| 6 |
Correct |
826 ms |
208228 KB |
Output is correct |
| 7 |
Incorrect |
857 ms |
235220 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
133 ms |
42432 KB |
Output is correct |
| 2 |
Execution timed out |
4100 ms |
701980 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
133 ms |
42432 KB |
Output is correct |
| 2 |
Execution timed out |
4100 ms |
701980 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
340 KB |
Output is correct |
| 4 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
