Submission #404145

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
404145	2021-05-13T22:09:50 Z	JerryLiu06	Walk (CEOI06_walk)	C++17	98 / 100	143 ms	11312 KB

walk

#include <bits/stdc++.h>
 
using namespace std;
 
using ll = long long;
using db = long double;
using str = string;
 
using pi = pair<int, int>;
using pl = pair<ll, ll>;
using pd = pair<db, db>;
 
using vi = vector<int>;
using vb = vector<bool>;
using vl = vector<ll>;
using vd = vector<db>;
using vs = vector<str>;
using vpi = vector<pi>;
using vpl = vector<pl>;
using vpd = vector<pd>;
 
#define mp make_pair
#define f first
#define s second

#define sz(x) (int)(x).size()
#define bg(x) begin(x)
#define all(x) bg(x), end(x)
#define sor(x) sort(all(x))
#define ft front()
#define bk back()
#define pb push_back
#define pf push_front
 
#define lb lower_bound
#define ub upper_bound
 
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define F0R(i, a) FOR(i, 0, a)
#define ROF(i, a, b) for (int i = (b) - 1; i >= (a); i--)
#define R0F(i, a) ROF(i, 0, a)
#define EACH(a, x) for (auto& a : x)

const int MOD = 1e9 + 7;
const int MX = 1e5 + 10;
const ll INF = 1e18;

using pp = pair<pi, pi>;
using pip = pair<int, pl>;

int X, Y, N; vector<pp> R; set<pip> active; // {Y, {X, dist}}

map<pip, pip> par;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);

    cin >> X >> Y >> N; F0R(i, N) { 
        int X1, Y1, X2, Y2; cin >> X1 >> Y1 >> X2 >> Y2;

        if (X1 > X2) swap(X1, X2); if (Y1 > Y2) swap(Y1, Y2); 
        
        if (X1 <= X) R.pb({{X1, Y1}, {X2, Y2}});
    }
    sort(all(R)); active.insert({0, {0, 0}});
    
    EACH(P, R) {
        int X1 = P.f.f; int Y1 = P.f.s; int X2 = P.s.f; int Y2 = P.s.s;

        pip comp; comp = {Y1, {-INF, -INF}}; ll dTop = INF; ll dBot = INF; pip top, bot;

        while (active.lb(comp) != active.end()) {
            pip cur = *active.lb(comp); if (cur.f > Y2) break;

            ll D1 = cur.s.s + ((X1 - 1) - cur.s.f) + ((Y2 + 1) - cur.f);
            ll D2 = cur.s.s + ((X1 - 1) - cur.s.f) + (cur.f - (Y1 - 1));

            if (D1 < dTop) { dTop = D1; top = {Y2 + 1, {X1 - 1, D1}}; par[top] = cur; }
            if (D2 < dBot) { dBot = D2; bot = {Y1 - 1, {X1 - 1, D2}}; par[bot] = cur; }

            active.erase(cur);
        }
        if (dTop != INF && dBot != INF) active.insert(top), active.insert(bot);
    }
    ll res = INF; vector<pl> ans; pip last;
    
    EACH(P, active) if (res > P.s.s + abs(X - P.s.f) + abs(Y - P.f)) res = P.s.s + abs(X - P.s.f) + abs(Y - P.f), last = P;
    
    cout << res << "\n"; ans.pb({0, Y - last.f}); ans.pb({X - last.s.f, 0});

    while (last != pip{0, {0, 0}}) {
        pip cur = par[last]; ans.pb({0, last.f - cur.f}); ans.pb({last.s.f - cur.s.f, 0}); last = par[last];
    }
    int st = 0; if (ans.front() == pl{0, 0}) st = 1;
    
    cout << sz(ans) - st << "\n"; ROF(i, st, sz(ans)) cout << ans[i].f << " " << ans[i].s << "\n";
}

Compilation message

walk.cpp: In function 'int main()':
walk.cpp:61:9: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   61 |         if (X1 > X2) swap(X1, X2); if (Y1 > Y2) swap(Y1, Y2);
      |         ^~
walk.cpp:61:36: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   61 |         if (X1 > X2) swap(X1, X2); if (Y1 > Y2) swap(Y1, Y2);
      |                                    ^~
walk.cpp:68:45: warning: unused variable 'X2' [-Wunused-variable]
   68 |         int X1 = P.f.f; int Y1 = P.f.s; int X2 = P.s.f; int Y2 = P.s.s;
      |                                             ^~

Subtask #1

98.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	1 ms	204 KB	Output is correct
3	Correct	1 ms	204 KB	Output is correct
4	Correct	2 ms	320 KB	Output is correct
5	Correct	91 ms	9104 KB	Output is correct
6	Correct	23 ms	2372 KB	Output is correct
7	Correct	35 ms	2640 KB	Output is correct
8	Partially correct	55 ms	2512 KB	Partially correct (80% score). Path intersects a building.
9	Correct	143 ms	11304 KB	Output is correct
10	Correct	116 ms	11312 KB	Output is correct