Submission #770191

#TimeUsernameProblemLanguageResultExecution timeMemory
770191danikoynovWalk (CEOI06_walk)C++14
0 / 100
133 ms44616 KiB
#include <bits/stdc++.h> #define endl "\n" using namespace std; typedef long long ll; void speed() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); } const int maxn = 1e5 + 10, maxc = 10000; /// fix this struct point { int x, y; void read() { cin >> x >> y; } point(int _x = 0, int _y = 0) { x = _x; y = _y; } }; struct rectangle { point A, B; void read() { A.read(); B.read(); } } r[maxn]; struct line { int x, y, len; int type; int idx; line(int _x, int _y, int _len, int _type, int _idx) { type = _type; x = _x; y = _y; len = _len; idx = _idx; } bool operator < (const line &l) const { if (x == l.x) return type > l.type; return x < l.x; } }; int st_x, st_y, n; void read() { cin >> st_x >> st_y >> n; for (int i = 1; i <= n; i ++) { r[i].A.read(); r[i].B.read(); if (r[i].A.x > r[i].B.x) swap(r[i].A.x, r[i].B.x); if (r[i].A.y > r[i].B.y) swap(r[i].A.y, r[i].B.y); r[i].A.y += maxc; r[i].B.y += maxc; } st_y += maxc; } int sub[2 * maxn]; vector < int > adj[2 * maxn]; stack < int > st[maxc * 2]; int used[2 * maxn]; void dfs(int v) { used[v] = 1; ///cout << v << " " << sub[v] << endl; if (adj[v].size() == 0) return; sub[v] = 1e9; for (int u : adj[v]) { if (!used[u]) dfs(u); int edge; int sx, sy, ex, ey; if (v == 0) { sx = 0; sy = maxc; } else if (v <= n) { sx = r[v].B.x; sy = r[v].A.y - 1; } else { sx = r[v - n].B.x; sy = r[v - n].B.y + 1; } if (u <= n) { ex = r[u].B.x; ey = r[u].A.y - 1; } else { ex = r[u - n].B.x; ey = r[u - n].B.y + 1; } edge = abs(sx - ex) + abs(sy - ey); ///cout << "edge " << v << " " << u << " " << edge << endl; ///cout << sx << " :: " << sy << " :: " << ex << " " << ey << endl; sub[v] = min(sub[v], sub[u] + edge); } ///cout << v << " " << sub[v] << endl; } void sweep_line() { vector < line > events; for (int i = 1; i <= n; i ++) { line l(r[i].A.x, r[i].A.y, r[i].B.y - r[i].A.y + 1, 1, i); events.push_back(l); } line sp(st_x, st_y, -1, 3, -1); events.push_back(sp); st[maxc].push(0); for (int i = 0; i < events.size(); i ++) { line l = events[i]; if (l.type == 3) { for (int j = 0; j < 2 * maxc; j ++) { while(!st[j].empty()) { int ver = st[j].top(); st[j].pop(); int idx = ver; if (idx > n) idx -= n; if (ver <= n) { if (ver == 0) sub[ver] = st_x + abs(st_y - maxc); else sub[ver] = abs(r[ver].A.y - 1 - st_y) + abs(st_x - r[ver].B.x); ///cout << "ver " << sub[ver] << " " << ver << endl; ///cout << abs(r[ver].A.y - 1 - st_y) << endl; } else { sub[ver] = abs(r[ver - n].B.y + 1 - st_y) + abs(st_x - r[ver - n].B.x); } } } break; } for (int j = l.y; j < l.y + l.len; j ++) { while(!st[j].empty()) { ///cout << l.idx << endl; adj[st[j].top()].push_back(l.idx); adj[st[j].top()].push_back(l.idx + n); st[j].pop(); } } ///cout << "here " << i << " " << l.idx << endl; st[l.y - 1].push(l.idx); st[l.y + l.len].push(l.idx + n); } } void solve() { read(); sweep_line(); dfs(0); cout << sub[0] << endl; } int main() { solve(); return 0; } /** 10 2 2 1 -1 3 3 5 -1 8 3 */

Compilation message (stderr)

walk.cpp: In function 'void sweep_line()':
walk.cpp:155:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<line>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  155 |     for (int i = 0; i < events.size(); i ++)
      |                     ~~^~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...