제출 #1075379

#제출 시각아이디문제언어결과실행 시간메모리
1075379HD1Sky Walking (IOI19_walk)C++14
0 / 100
921 ms279128 KiB
#include "walk.h" #include<bits/stdc++.h> #define pb push_back #define ff first #define ss second #define sz(x) ll(x.size()) #define all(x) x.begin(),x.end() using namespace std; typedef long long ll; typedef pair<int,int> ii; const ll MAX=1e6+10; const ll inf=1e9; vector<ii>gfo[MAX]; int cur[MAX], dist[MAX]; void dikstra(int ini){ set<ii> q; q.insert({0,ini}); dist[ini]=0; while(sz(q)){ auto x=*q.begin(); q.erase(q.begin()); int u=x.ss; int dist_u=x.ff; if(dist_u!=dist[u])continue; for(auto y:gfo[u]){ int w=y.ss; int v=y.ff; if(dist[v]>dist[u]+w){ dist[v]=dist[u]+w; q.insert({dist[v], v}); } } } } map< pair<int,int>, int> M; long long min_distance(vector<int> x,vector<int> h, vector<int> l,vector<int> r, vector<int> y, int s, int g) { vector<pair<int,ii>> c; ll m=sz(y);//numero de rascacielos ll n=sz(x);//numero de torres for(int i=0; i<m; i++){ c.pb({y[i],{l[i],r[i]}});// por su altura } sort(all(c)); ll nod=0, nod_prev=0, mx=0, pos=0; for(int i=0; i<n; i++){ if(!M.count({x[i], 0})){ M[{x[i],0}]=mx+1; mx++; cur[i]=0;//altura } } for(auto q:c){//rascacielo en la altura q.ff int alt=q.ff; int l=q.ss.ff; int r=q.ss.ss; for(int i=l; i<=r; i++){ if(alt<=h[i]){// hay interseccion if(!M.count({x[i],alt})){ M[{x[i],alt}]=mx+1; mx++; } nod = M[{x[i], alt}]; // verical gfo[nod].pb({M[{x[i],cur[i]}], alt-cur[i]}); gfo[M[{x[i],cur[i]}]].pb({nod, alt-cur[i]}); cur[i]=alt; if(i==l){ nod_prev=nod; pos=x[l]; continue; } //horizontal gfo[nod].pb({nod_prev,x[i]-pos}); gfo[nod_prev].pb({nod,x[i]-pos}); pos = x[i];// ultima posicion de interseccion nod_prev = nod;// nombre del nodo anterior } } } // for(auto a:M){ // cout<<a.ff.ff<<' '<<a.ff.ss<<" -> "<<a.ss<<'\n'; // } // for(auto a:M){ // cout<<a.ss<<" -> "; // for(auto b:gfo[a.ss]){ // cout<<b.ff<<", "<<b.ss; // cout<<'\n'; // } // cout<<'\n'; // } for(int i=0; i<=mx; i++)dist[i]=inf; dikstra(M[{x[s],0}]); ll ans=dist[M[{x[g],0}]]; return ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...