Submission #1161185

#	Time	Username	Problem	Language	Result	Execution time	Memory
1161185		wanglingyun9	Walk (CEOI06_walk)	C++17	40 / 100	118 ms	39204 KiB

walk

#include <bits/stdc++.h>
using namespace std;
 
// ---------------- Structures ------------------
 
struct Building {
    int r;      // right coordinate = max(x1,x2)
    int lower;  // min(y1,y2)
    int upper;  // max(y1,y2)
    int id;     // building id
};
 
// Candidate point (a “corner”)
struct Candidate {
    int x, y;    // coordinates
    int type;    // 0: TU (upper candidate), 1: TD (lower candidate)
    int bID;     // building id (for TU/TD); for dummy candidate (destination) we set bID = -1.
    int nxt;     // the building id (T) encountered when “looking left” from this candidate; -1 if none.
    long long dp;  // DP value: minimum distance from S=(0,0) to this candidate along a special path.
    int parent;    // predecessor candidate index in the DP chain.
};
 
// Sweep–line event
// For buildings: type 0 = activation (at y = lower), type 1 = deactivation (at y = upper).
// For candidate queries: type 2 = query for TD candidate (at candidate.y), type 3 = query for TU candidate (at candidate.y).
struct Event {
    int y;
    int type;    // 0: activate, 1: deactivate, 2: query TD, 3: query TU
    int x;       // x coordinate of the event (for building events: building r)
    int bID;     // building id for activate/deactivate; -1 otherwise.
    int candIdx; // candidate index (for query events)
};
 
// ---------------- Segment Tree ------------------
 
struct SegNode {
    int val; // store the x coordinate (r value) of the building currently active at that index.
    int bID; // building id.
};
 
struct SegmentTree {
    int size;
    vector<SegNode> tree;
    SegmentTree(int n) {
        size = 1;
        while(size < n) size *= 2;
        tree.assign(2 * size, {-1, -1});
    }
    void update(int pos, int val, int bID) {
        pos += size;
        tree[pos] = {val, bID};
        for(pos /= 2; pos >= 1; pos /= 2) {
            if(tree[2*pos].val >= tree[2*pos+1].val)
                tree[pos] = tree[2*pos];
            else
                tree[pos] = tree[2*pos+1];
        }
    }
    SegNode query(int l, int r) {
        SegNode res = {-1, -1};
        l += size; r += size;
        while(l <= r) {
            if(l % 2 == 1) {
                if(tree[l].val > res.val) res = tree[l];
                l++;
            }
            if(r % 2 == 0) {
                if(tree[r].val > res.val) res = tree[r];
                r--;
            }
            l /= 2; r /= 2;
        }
        return res;
    }
};
 
// ---------------- Helper ------------------
 
inline long long manhattan(int x1, int y1, int x2, int y2) {
    return (long long) abs(x1 - x2) + abs(y1 - y2);
}
 
// ---------------- Main ------------------
 
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int X, Y, N;
    cin >> X >> Y >> N;
    vector<Building> buildings;
    buildings.reserve(N);
    for (int i = 0; i < N; i++){
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        int r = max(x1, x2);
        int lower = min(y1, y2);
        int upper = max(y1, y2);
        buildings.push_back({r, lower, upper, i});
    }
 
    // ---------------- Build Candidate Points ------------------
    // For each building T, create:
    //   TU: (T.r, T.upper+1) and TD: (T.r, T.lower-1)
    // Also add dummy candidate for destination D = (X,Y).
    vector<Candidate> cand;
    cand.reserve(2 * N + 1);
    // To quickly find a building’s candidates:
    vector<int> candTU(N, -1), candTD(N, -1);
    for (int i = 0; i < N; i++){
        Candidate c;
        c.x = buildings[i].r;
        c.y = buildings[i].upper + 1;
        c.type = 0; // TU
        c.bID = buildings[i].id;
        c.nxt = -1;
        c.dp = 0;
        c.parent = -1;
        cand.push_back(c);
        candTU[buildings[i].id] = cand.size() - 1;
 
        c.x = buildings[i].r;
        c.y = buildings[i].lower - 1;
        c.type = 1; // TD
        c.bID = buildings[i].id;
        c.nxt = -1;
        c.dp = 0;
        c.parent = -1;
        cand.push_back(c);
        candTD[buildings[i].id] = cand.size() - 1;
    }
    // Dummy candidate for destination.
    Candidate dummy;
    dummy.x = X; dummy.y = Y;
    // Treat dummy as a TU candidate.
    dummy.type = 0;
    dummy.bID = -1;
    dummy.nxt = -1;
    dummy.dp = 0;
    dummy.parent = -1;
    cand.push_back(dummy);
    int dummyIdx = cand.size() - 1;
 
    // ---------------- Build Sweep–line Events ------------------
    vector<Event> events;
    events.reserve(2 * N + cand.size());
    for (int i = 0; i < N; i++){
        Event ev;
        ev.y = buildings[i].lower;
        ev.type = 0; // activation
        ev.x = buildings[i].r;
        ev.bID = buildings[i].id;
        ev.candIdx = -1;
        events.push_back(ev);
 
        ev.y = buildings[i].upper;
        ev.type = 1; // deactivation
        ev.x = buildings[i].r;
        ev.bID = buildings[i].id;
        ev.candIdx = -1;
        events.push_back(ev);
    }
    // For candidate queries:
    // For TU (type==0) candidates: query at y = candidate.y with event type 3.
    // For TD (type==1) candidates: query at y = candidate.y with event type 2.
    for (int i = 0; i < (int)cand.size(); i++){
        Event ev;
        ev.y = cand[i].y;
        if(cand[i].type == 0) { // TU (or dummy)
            ev.type = 3; // query TU
        } else { // TD
            ev.type = 2; // query TD
        }
        ev.x = cand[i].x;
        ev.candIdx = i;
        ev.bID = -1;
        events.push_back(ev);
    }
    // Sort events by y; if equal, by type (activation < query < deactivation)
    sort(events.begin(), events.end(), [](const Event &a, const Event &b) {
        if(a.y == b.y) return a.type < b.type;
        return a.y < b.y;
    });
 
    // ---------------- Process Events with Segment Tree ------------------
    const int MAXX = 1000002;
    SegmentTree seg(MAXX);
    for(auto &ev : events){
        if(ev.type == 0) { // activation
            seg.update(ev.x, ev.x, ev.bID);
        } else if(ev.type == 1) { // deactivation
            seg.update(ev.x, -1, -1);
        } else if(ev.type == 2 || ev.type == 3) { // query events
            SegNode res = seg.query(0, ev.x);
            cand[ev.candIdx].nxt = res.bID; // -1 if none found
        }
    }
 
    // ---------------- DP: Process Candidates in increasing order of x (and type order)
    // Order: sort by (x ascending, then type where TU (0) comes before TD (1))
    vector<int> order(cand.size());
    for (int i = 0; i < (int)cand.size(); i++)
        order[i] = i;
    sort(order.begin(), order.end(), [&](int a, int b) {
        if(cand[a].x == cand[b].x)
            return cand[a].type < cand[b].type;
        return cand[a].x < cand[b].x;
    });
 
    const long long INF = 1LL << 60;
    vector<long long> dp(cand.size(), INF);
    vector<int> par(cand.size(), -1);
 
    // Base: For any candidate with no blocking building (nxt == -1), dp = x + |y|
    for (int idx : order) {
        if(cand[idx].nxt == -1) {
            dp[idx] = cand[idx].x + (long long) abs(cand[idx].y);
            par[idx] = -1;
        } else {
            int r = cand[idx].nxt; // building id that blocks candidate idx
            int idxTU = candTU[r];
            int idxTD = candTD[r];
            long long opt1 = dp[idxTU] + manhattan(cand[idx].x, cand[idx].y, cand[idxTU].x, cand[idxTU].y);
            long long opt2 = dp[idxTD] + manhattan(cand[idx].x, cand[idx].y, cand[idxTD].x, cand[idxTD].y);
            if(opt1 <= opt2) {
                dp[idx] = opt1;
                par[idx] = idxTU;
            } else {
                dp[idx] = opt2;
                par[idx] = idxTD;
            }
        }
        // If two candidates come from the same building (i.e. same x and same bID, and bID != -1),
        // update both to the same (minimum) dp value.
        if(cand[idx].bID != -1) {
            // Look ahead in order for another candidate from the same building
            // (since buildings produce exactly two candidates).
            // (They have the same x; our sort order ensures TU comes before TD.)
            // We can update both.
            // Find next candidate with same x and same building id.
            int j = idx + 1;
            if(j < (int)order.size()){
                int idx2 = order[j];
                if(cand[idx2].bID == cand[idx].bID && cand[idx2].x == cand[idx].x) {
                    long long bestVal = min(dp[idx], dp[idx2]);
                    dp[idx] = dp[idx2] = bestVal;
                }
            }
        }
    }
    // Save DP and parent info back to candidates.
    for (int i = 0; i < (int)cand.size(); i++){
        cand[i].dp = dp[i];
        cand[i].parent = par[i];
    }
 
    // The answer is the dp for the dummy candidate.
    long long ans = cand[dummyIdx].dp;
 
    // ---------------- Reconstruct the Candidate Chain ------------------
    vector<int> chain;
    int cur = dummyIdx;
    while(cur != -1) {
        chain.push_back(cur);
        cur = cand[cur].parent;
    }
    reverse(chain.begin(), chain.end());
    // Now chain[0] will be the candidate reached directly from S.
    // (S itself is not among the candidates.)
 
    // ---------------- Reconstruct the Path Polyline ------------------
    // We now “simulate” the special path using a safe routing rule:
    // • From S = (0,0) to the first candidate P:
    //    – Since S is not attached to a building, we “exit” safely by moving vertically first,
    //      then horizontally.
    // • From a candidate (which is on a building’s boundary) to the next candidate,
    //    the only safe move is to continue horizontally (to stay on the building boundary)
    //    and then change vertically.
    vector<pair<int,int>> polyline;
    // Start at S = (0,0)
    polyline.push_back({0,0});
    // If there is at least one candidate in the chain, define P0 = chain[0]'s coordinates.
    // For leg 0 (from S to chain[0]): use vertical-then-horizontal.
    if(!chain.empty()){
        int idx = chain[0];
        int targetX = cand[idx].x;
        int targetY = cand[idx].y;
        // Vertical move from (0,0) to (0, targetY)
        polyline.push_back({0, targetY});
        // Horizontal move from (0, targetY) to (targetX, targetY)
        polyline.push_back({targetX, targetY});
    }
    // For subsequent legs (from candidate i to candidate i+1), use horizontal-first.
    for (size_t i = 0; i + 1 < chain.size(); i++){
        int currIdx = chain[i];
        int nextIdx = chain[i+1];
        int currX = cand[currIdx].x, currY = cand[currIdx].y;
        int nextX = cand[nextIdx].x, nextY = cand[nextIdx].y;
        // From current candidate, move horizontally to nextX while staying at currY.
        polyline.push_back({nextX, currY});
        // Then move vertically from (nextX, currY) to (nextX, nextY).
        polyline.push_back({nextX, nextY});
    }
 
    // ---------------- Compress Polyline Segments ------------------
    // Merge consecutive segments in the same direction.
    vector<pair<int,int>> segments;
    // First compute segments from polyline points.
    vector<pair<int,int>> pts = polyline;
    // Remove consecutive duplicate points.
    vector<pair<int,int>> clean;
    clean.push_back(pts[0]);
    for (size_t i = 1; i < pts.size(); i++){
        if(pts[i] != clean.back())
            clean.push_back(pts[i]);
    }
    for (size_t i = 0; i + 1 < clean.size(); i++){
        int dx = clean[i+1].first - clean[i].first;
        int dy = clean[i+1].second - clean[i].second;
        segments.push_back({dx, dy});
    }
    // Further compress if two consecutive segments are in the same direction.
    vector<pair<int,int>> comp;
    if(!segments.empty()){
        comp.push_back(segments[0]);
        for (size_t i = 1; i < segments.size(); i++){
            auto &last = comp.back();
            // Same direction if both dx are zero or both dy are zero.
            if((last.first == 0 && segments[i].first == 0) ||
               (last.second == 0 && segments[i].second == 0)){
                last.first += segments[i].first;
                last.second += segments[i].second;
            } else {
                comp.push_back(segments[i]);
            }
        }
    }
 
    // ---------------- Output ------------------
    cout << ans << "\n";
    cout << comp.size() << "\n";
    for (auto &seg : comp)
        cout << seg.first << " " << seg.second << "\n";
 
    return 0;
}

• Subtask 1: 40 / 100