제출 #1067657

#제출 시각아이디문제언어결과실행 시간메모리
1067657jerzykSky Walking (IOI19_walk)C++17
0 / 100
196 ms110672 KiB
#include <bits/stdc++.h> #include "walk.h" using namespace std; #define pb push_back #define st first #define nd second typedef long long ll; typedef long double ld; const ll I = 1000LL * 1000LL * 1000LL * 1000LL * 1000LL * 1000LL; const int II = 2 * 1000 * 1000 * 1000; const ll M = 1000LL * 1000LL * 1000LL + 7LL; const int N = 1<<18; const int NN = 1<<20; int tab[NN], hei[NN]; int drz[2 * N], drz2[2 * N]; int cnt = 0; pair<int, int> co[NN]; vector<pair<int, ll>> ed[NN]; ll dis[NN]; pair<pair<int, int>, int> wal[NN]; bool vis[NN]; vector<int> poi[NN]; vector<int> sky[NN]; void DoDrz(int n) { for(int i = 1; i <= n; ++i) drz[i + N] = hei[i]; for(int i = 1; i <= n; ++i) drz2[i + N] = 1; for(int i = N - 1; i >= 1; --i) drz[i] = max(drz[i * 2], drz[i * 2 + 1]); for(int i = N - 1; i >= 1; --i) drz2[i] = drz2[i * 2] + drz2[i * 2 + 1]; } int Find(int a, int b, int x, int r) { a += N - 1; b += N + 1; int a1 = 0, a2 = 0, b1 = 0, b2 = 0; while(a / 2 != b / 2) { if(a % 2 == 0 && drz[a + 1] >= x) { if(a1 == 0) a1 = a + 1; a2 = a + 1; } if(b % 2 == 1 && drz[b - 1] >= x) { if(b1 == 0) b1 = b - 1; b2 = b - 1; } a /= 2; b /= 2; } if(r == 0) a = a1; if(a == 0) a = b2; if(r == 1) a = b1; if(a == 0) a = a2; while(a < N) { a = a * 2 + r; if(drz[a] < x) a ^= 1; } return a - N; } bool C(pair<pair<int, int>, int> a, pair<pair<int, int>, int> b) { return (make_pair(a.nd, a.st) < make_pair(b.nd, b.st)); } void Clr(int v, int a, int b, int pz, int kz, int id) { if(drz2[v] <= 0 || a > kz || b < pz) return; if(v >= N) { v -= N; //cerr << "clr: " << v << " " << id << "\n"; if(hei[v] >= wal[id].nd) sky[v].pb(id); --drz2[v + N]; return; } Clr(v * 2, a, (a + b) / 2, pz, kz, id); Clr(v * 2 + 1, (a + b) / 2 + 1, b, pz, kz, id); drz2[v] = drz2[v * 2] + drz2[v * 2 + 1]; } inline ll D(int i, int j) { ll d1 = max(co[i].st - co[j].st, co[j].st - co[i].st); ll d2 = max(co[i].nd - co[j].nd, co[j].nd - co[i].nd); return d1 + d2; } inline void A(int x, int y) { ll d = D(x, y); ed[x].pb(make_pair(y, d)); ed[y].pb(make_pair(x, d)); } void SanInput(int n, int &k, int u, int v) { int dod = 0; sort(wal + 1, wal + 1 + k, C); for(int i = 1; i <= k; ++i) { //cerr << "skypath: " << i << " " << wal[i].st.st - 1 << " " << wal[i].st.nd - 1 << " " << wal[i].nd << "\n"; vector<int> cur = {wal[i].st.st, wal[i].st.nd}, hl; if(wal[i].st.st < u && wal[i].st.nd > u) { int v1 = Find(1, u, wal[i].nd, 1), v2 = Find(u, n, wal[i].nd, 0); cur.pb(v1); cur.pb(v2); } if(wal[i].st.st < v && wal[i].st.nd > v) { int v1 = Find(1, v, wal[i].nd, 1), v2 = Find(v, n, wal[i].nd, 0); cur.pb(v1); cur.pb(v2); } sort(cur.begin(), cur.end()); for(int j = 0; j < (int)cur.size(); ++j) if(j == 0 || cur[j] != cur[j - 1]) hl.pb(cur[j]); cur = hl; wal[i].st.nd = cur[1]; Clr(1, 0, N - 1, wal[i].st.st, wal[i].st.nd, i); sky[cur[0]].pb(i); sky[cur[1]].pb(i); for(int j = 1; j < (int)cur.size() - 1; ++j) { ++dod; wal[k + dod] = make_pair(make_pair(cur[j], cur[j + 1]), wal[i].nd); Clr(1, 0, N - 1, wal[k + dod].st.st, wal[k + dod].st.nd, i); sky[cur[j]].pb(k + dod); sky[cur[j + 1]].pb(k + dod); } //for(int j = 1; j < (int)cur.size() - 1; ++j) //{ //cerr << cur[j] - 1 << " "; //} //cerr << "\n"; } k += dod; cnt = n; for(int i = 1; i <= n; ++i) { //vector<int> hlp; //for(int j = 0; j < (int)sky[i].size(); ++j) //if(j == 0 || sky[i][j] != sky[i][j - 1]) hlp.pb(sky[i][j]); //ssky[i] = hlp; co[i] = make_pair(tab[i], 0); int pr = i; //cerr << "Sky: " << i << " " << "\n"; for(int j = 0; j < (int)sky[i].size(); ++j) { if(j != 0) pr = cnt; if(j == 0 || wal[sky[i][j]].nd != wal[sky[i][j - 1]].nd) {++cnt; co[cnt] = make_pair(tab[i], wal[sky[i][j]].nd); A(cnt, pr);} poi[sky[i][j]].pb(cnt); //cerr << sky[i][j] << " "; } //cerr << "\n"; } for(int i = 1; i <= k; ++i) for(int j = 1; j < (int)poi[i].size(); ++j) A(poi[i][j - 1], poi[i][j]); } void Dijkstra(int s) { int n = cnt; priority_queue<pair<ll, int>> q; for(int i = 1; i <= n; ++i) dis[i] = I; dis[s] = 0LL; q.push(make_pair(0LL, s)); while((int)q.size() > 0) { int v = q.top().nd; q.pop(); if(vis[v]) continue; vis[v] = true; //cerr << "Dijkstra: " << v << " " << co[v].st << " " << co[v].nd << " " << dis[v] << "\n"; for(int i = 0; i < (int)ed[v].size(); ++i) { //cout << "ed: " << ed[v][i].st << " " << ed[v][i].nd << "\n"; ll d = dis[v] + ed[v][i].nd; if(d < dis[ed[v][i].st]) { dis[ed[v][i].st] = d; q.push(make_pair(-d, ed[v][i].st)); } } } } long long min_distance(vector<int> _x, vector<int> _h, vector<int> _l, vector<int> _r, vector<int> _y, int _s, int _g) { int u = _s + 1, v = _g + 1; int n = _x.size(), k = _l.size(); for(int i = 1; i <= n; ++i) {tab[i] = _x[i - 1]; hei[i] = _h[i - 1]; ++cnt;} for(int i = 1; i <= k; ++i) wal[i] = make_pair(make_pair(_l[i - 1] + 1, _r[i - 1] + 1), _y[i - 1]); DoDrz(n); SanInput(n, k, u, v); Dijkstra(u); if(dis[v] == I) return -1; return dis[v]; }
#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...