Submission #1108732

#	Time	Username	Problem	Language	Result	Execution time	Memory
1108732		mariaclara	도넛 (JOI14_ho_t3)	C++17	0 / 100	3 ms	15184 KiB

2014_ho_t3

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef tuple<ll,ll,ll> trio;
typedef pair<int,int> pii;
const int MAXN = 2e5+5;
const ll INF = 1e12;
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#define mk make_pair
#define pb push_back
#define fr first
#define sc second

int l, c, n, ord[MAXN];
ll dist[2][MAXN];
pii p[MAXN];
vector<trio> edges[2][MAXN];

int dijkstra() {
    fill(dist[0], dist[0] + n + 2, INF);
    fill(dist[1], dist[1] + n + 2, INF);
    priority_queue<trio, vector<trio>, greater<trio>> pq;
    pq.push({0, 0, 1});

    while(!pq.empty()) {
        auto [D, no, flag] = pq.top();
        pq.pop();

        if(dist[flag][no] < INF) continue;
        dist[flag][no] = D;

        for(auto [new_flag, viz, peso] : edges[flag][no])
            if(D + peso < dist[new_flag][viz])
                pq.push({D + peso, viz, new_flag});
    }

    if(dist[0][n+1] == INF and dist[1][n+1] == INF) return -1;
    return min(dist[0][n+1], dist[1][n+1]);
}
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> l >> c >> n;

    for(int i = 1; i <= n; i++) {
        cin >> p[i].fr >> p[i].sc;
        edges[0][i].pb({1, i, 1});
        edges[1][i].pb({0, i, 1});
        ord[i] = i;
    }

    sort(ord+1, ord+1+n, [](int a, int b){
        if(p[a].sc != p[b].sc) return p[a].sc < p[b].sc;
        return p[a].fr < p[b].fr;
    });

    if(p[ord[1]].sc == 1) {
        edges[0][ord[1]].pb({0, 0, p[ord[1]].fr - 1});
        edges[0][0].pb({0, ord[1], p[ord[1]].fr - 1});
    }

    if(p[ord[n]].sc == c) {
        edges[0][ord[n]].pb({0, n+1, l - p[ord[n]].fr});
        edges[0][n+1].pb({0, ord[n], l - p[ord[n]].fr});
    }

    for(int i = 1; i < n; i++) {
        if(p[ord[i]].sc != p[ord[i+1]].sc) continue;
        edges[0][ord[i]].pb({0, ord[i+1], p[ord[i+1]].fr - p[ord[i]].fr});
        edges[0][ord[i+1]].pb({0, ord[i], p[ord[i+1]].fr - p[ord[i]].fr});
    }

    sort(ord+1, ord+1+n, [](int a, int b){
        return p[a] < p[b];
    });

    if(p[ord[1]].fr == 1) {
        edges[1][ord[1]].pb({1, 0, p[ord[1]].sc - 1});
        edges[1][0].pb({1, ord[1], p[ord[1]].sc - 1});
    }

    if(p[ord[n]].fr == l) {
        edges[1][ord[n]].pb({1, n+1, c - p[ord[n]].sc});
        edges[1][n+1].pb({1, ord[n], c - p[ord[n]].sc});
    }
    
    for(int i = 1; i < n; i++) {
        if(p[ord[i]].fr != p[ord[i+1]].fr) continue;
        edges[1][ord[i]].pb({1, ord[i+1], p[ord[i+1]].sc - p[ord[i]].sc});
        edges[1][ord[i+1]].pb({1, ord[i], p[ord[i+1]].sc - p[ord[i]].sc});
    }

    cout << dijkstra();
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 15
• Subtask 3: 0 / 30
• Subtask 4: 0 / 50