제출 #293868

#제출 시각아이디문제언어결과실행 시간메모리
293868PeppaPigSky Walking (IOI19_walk)C++14
10 / 100
4019 ms283988 KiB
#include "walk.h" #include <bits/stdc++.h> #define long long long #define pii pair<long, long> #define x first #define y second using namespace std; const int N = 1.2e6 + 5; int n, m; long dp[N]; vector<pii> coord, g[N]; vector<int> inter[N]; int get(pii x) { return lower_bound(coord.begin(), coord.end(), x) - coord.begin(); } long min_distance(vector<int> x, vector<int> h, vector<int> l, vector<int> r, vector<int> y, int su, int eu) { n = (int)x.size(), m = (int)l.size(); coord.emplace_back(x[su], 0), coord.emplace_back(x[eu], 0); for(int i = 0; i < m; i++) for(int j = l[i]; j <= r[i]; j++) { if(h[j] < y[i]) continue; coord.emplace_back(x[j], y[i]); } sort(coord.begin(), coord.end()); coord.resize(unique(coord.begin(), coord.end()) - coord.begin()); //for(pii p : coord) printf("(%lld %lld)\n", p.x, p.y); inter[su].emplace_back(0), inter[eu].emplace_back(0); for(int i = 0; i < m; i++) for(int j = l[i], p = -1, d = -1; j <= r[i]; j++) { if(h[j] < y[i]) continue; int u = get(pii(x[j], y[i])); if(p != -1) { g[u].emplace_back(p, x[j] - d), g[p].emplace_back(u, x[j] - d); //printf("edge (%lld %lld) (%lld %lld) = %d\n", coord[u].x, coord[u].y, coord[p].x, coord[p].y, x[j] - d); } p = u, d = x[j]; inter[j].emplace_back(y[i]); } for(int i = 0; i < n; i++) { sort(inter[i].begin(), inter[i].end()); inter[i].resize(unique(inter[i].begin(), inter[i].end()) - inter[i].begin()); while(!inter[i].empty() && inter[i].back() > h[i]) inter[i].pop_back(); for(int j = 0; j < (int)inter[i].size() - 1; j++) { int d = inter[i][j + 1] - inter[i][j]; int u = get(pii(x[i], inter[i][j])), v = get(pii(x[i], inter[i][j + 1])); g[u].emplace_back(v, d), g[v].emplace_back(u, d); //printf("edge (%lld %lld) (%lld %lld) = %d\n", coord[u].x, coord[u].y, coord[v].x, coord[v].y, d); } } fill_n(dp, N, 1e18); priority_queue<pii, vector<pii>, greater<pii> > Q; Q.emplace(dp[get(pii(x[su], 0))] = 0, get(pii(x[su], 0))); while(!Q.empty()) { pii u = Q.top(); Q.pop(); if(dp[u.y] != u.x) continue; for(pii v : g[u.y]) if(u.x + v.y < dp[v.x]) Q.emplace(dp[v.x] = u.x + v.y, v.x); } long ret = dp[get(pii(x[eu], 0))]; return ret == 1e18 ? -1 : ret; }
#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...