제출 #1188925

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1188925		caterpillow	Curtains (NOI23_curtains)	C++20	0 / 100	0 ms	524 KiB

curtains

#include <bits/stdc++.h>

#pragma GCC optimise("O3,unroll-loops");

using namespace std;

main() {
    cin.tie(0)->sync_with_stdio(0);
    
    int n, m; cin >> n >> m;
    if (n == 1) {
        cout << "0\n";
        return 0;
    }
    vector<int> h(n);
    for (int &x : h) cin >> x;
    vector<vector<int>> adj(n);    
    for (int i = 0; i < m; i++) {
        int u, v; cin >> u >> v; u--, v--;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    struct entry {
        int d, a, u;
        bool operator<(const entry &oth) const {
            return d > oth.d;
        }
    };

    auto funny_dijkstra = [&] (int s, vector<int> &dist, vector<int> &alt) {
        priority_queue<entry> pq;
        pq.push({h[s], h[s], s});
        while (pq.size()) {
            auto [d, a, u] = pq.top(); pq.pop();
            if (dist[u] < d) continue;
            dist[u] = d;
            alt[u] = a;
            for (int v : adj[u]) pq.push({max(d + 1, h[v]), max(alt[u], h[v]), v});
        }
    };

    vector<int> dist0(n, 1e9), dist1(n, 1e9), alt0(n), alt1(n);
    funny_dijkstra(0, dist0, alt0);
    funny_dijkstra(n - 1, dist1, alt1);
    int ans = 1e9;
    for (int i = 0; i < n; i++) {
        if (alt0[i] == alt1[i])
            ans = min(ans, dist0[i] + dist1[i]);
    }
    cout << ans << '\n';
}

컴파일 시 표준 에러 (stderr) 메시지

curtains.cpp:7:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
    7 | main() {
      | ^~~~

• Subtask 1: 0 / 3
• Subtask 2: 0 / 6
• Subtask 3: 0 / 15
• Subtask 4: 0 / 20
• Subtask 5: 0 / 36
• Subtask 6: 0 / 20