제출 #1213271

#제출 시각아이디문제언어결과실행 시간메모리
1213271guagua0407Sky Walking (IOI19_walk)C++20
10 / 100
4096 ms476772 KiB
#pragma GCC optimize("O3") #include "walk.h" //#include "grader.cpp" #include <bits/stdc++.h> using namespace std; #define ll long long #define pii pair<int,int> #define f first #define s second #define all(x) x.begin(),x.end() #define _ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); namespace{ const ll inf=(ll)1e18; } 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 s, int g) { auto st=clock(); int n=(int)x.size(); int m=(int)l.size(); vector<vector<int>> ys(n); for(int i=0;i<n;i++){ ys[i].push_back(0); } for(int i=0;i<m;i++){ for(int j=l[i];j<=r[i];j++){ if(y[i]<=h[j]){ ys[j].push_back(y[i]); } } } vector<int> id(n); int cnt=0; for(int i=0;i<n;i++){ sort(all(ys[i])); ys[i].resize(unique(all(ys[i]))-ys[i].begin()); id[i]=cnt; cnt+=(int)ys[i].size(); } vector<vector<pair<int,int>>> adj(cnt); auto add_edge=[&](int a,int b,int c){ adj[a].push_back({b,c}); adj[b].push_back({a,c}); }; for(int i=0;i<n;i++){ for(int j=0;j<(int)ys[i].size()-1;j++){ add_edge(id[i]+j,id[i]+j+1,ys[i][j+1]-ys[i][j]); } } for(int i=0;i<m;i++){ vector<pair<int,int>> tmp; for(int j=l[i];j<=r[i];j++){ if(y[i]<=h[j]){ int pos=lower_bound(all(ys[j]),y[i])-ys[j].begin(); tmp.push_back({j,id[j]+pos}); } } for(int j=0;j<(int)tmp.size()-1;j++){ add_edge(tmp[j].s,tmp[j+1].s,x[tmp[j+1].f]-x[tmp[j].f]); } } vector<ll> d(cnt,inf); priority_queue<pair<ll,int>,vector<pair<ll,int>>,greater<pair<ll,int>>> pq; d[id[s]]=0; pq.push({0,id[s]}); int en=id[g]; while(!pq.empty() and clock()-st<3*CLOCKS_PER_SEC){ auto v=pq.top(); pq.pop(); if(v.f!=d[v.s]) continue; if(v.s==en) return v.f; for(auto u:adj[v.s]){ if(clock()-st>3*CLOCKS_PER_SEC) break; if(d[v.s]+u.s<d[u.f]){ d[u.f]=d[v.s]+u.s; pq.push({d[u.f],u.f}); } } } return -1; }
#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...