제출 #1327428

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1327428		retarde	Airplane (NOI23_airplane)	C++20	0 / 100	1106 ms	281092 KiB

Main

#include <bits/stdc++.h>
using namespace std;

#define pb push_back
#define pf push_front
#define mp make_pair
#define fi first
#define se second
#define int long long
#define all(x) (x).begin(), (x).end()

typedef long double ld;
typedef long long ll;
typedef pair<ll,ll> pll;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<bool> vb;
typedef vector<vector<int>> vvi;
typedef vector<vector<bool>> vvb;
typedef vector<vector<ll>> vvll;
typedef vector<string> vs;
typedef vector<vector<string>> vvs;
typedef vector<char> vc;
typedef vector<vector<char>> vvc;
typedef map<int, int> mii;
typedef unordered_map<int, int> umii;

const int mod = 1e9 + 7;
const int inf = INTMAX_MAX;
const bool tc = false;

vi dijsktra(int s, int n, vector<vector<pii>> &adj) {
    vi d(n, 1e18);
    set<pii> st;
    st.insert({0, s});
    int cnt = 0; d[s] = 0;
    vi p(n);
    while (st.size()) {
        auto cur = *st.begin();
        st.erase(st.begin());
        // cout << "Node: " << cur.se << ", Dist:" << cur.fi << '\n';
        // if (cnt > 100) break;

        int node = cur.se;
        int dist = cur.fi;
        if (d[node] < dist) continue;
        // cout << "Neighbours:\n";
        for (auto &neighbour : adj[cur.se]) {   
            // cout << neighbour.fi << " " << neighbour.se << '\n';
            // cout << d[neighbour.fi] << " < " << d[node] << " + " << neighbour.se << " ?\n";
            if (d[neighbour.fi] <= d[node] + neighbour.se) continue;
            // cout << "No. Adding\n";
            // cout << "Adding.\n";
            // cout << node + 1 << " -> " << neighbour.fi + 1 << " with " << neighbour.se << '\n';
            p[neighbour.fi] = node;
            st.erase({d[neighbour.fi], neighbour.fi});
            d[neighbour.fi] = d[node] + neighbour.se;
            st.insert({d[neighbour.fi], neighbour.fi});
        }
        cnt++;
    }

    // cout << "D:\n";
    // for (auto &x : d) cout << x << " ";
    // cout << '\n';

    // cout << "P:\n";
    // for (auto &x : p) cout << x + 1 << " ";
    // cout << '\n';

    return d;
}

inline void solve() {
    int n, m;
    cin >> n >> m;
    vi a(n); for (int i = 0; i < n; i++) cin >> a[i];
    vvi iadj(n); for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        u--; v--;
        iadj[u].pb(v);
        iadj[v].pb(u);
    }    

    vector<vector<pii>> nadj(n);
    for (int s = 0; s < n; s++) {
        int v = a[s]; vi vis(n);
        queue<pii> bfs; bfs.push({s, 0});
        while (bfs.size()) {
            auto cur = bfs.front();
            bfs.pop();
            int node = cur.fi;
            if (vis[node]) continue;
            vis[node] = 1;
            // cout << "Started " << s << " at node " << node << " diff " << a[node] - a[s] << '\n';
            // cout << "Node " << node << ""
            nadj[s].pb({node, max((a[node] - a[s]), cur.se)});
            // nadj[s].pb({node, max(-(a[s] - a[node]), cur.se)});
            if (a[node] > a[s]) {
                continue;
            }
            for (auto &neighbour : iadj[node]) {
                if (vis[neighbour]) continue;
                bfs.push({neighbour, cur.se + 1});
            }
        }   
    }

    // for (int i = 0; i < n; i++) {
    //     for (auto &x : nadj[i]) {
    //         cout << i + 1 << " " << x.fi + 1 << " " << x.se << '\n';
    //     }
    // }

    vi d1 = dijsktra(0, n, nadj), d2 = dijsktra(n - 1, n, nadj);

    int ans = 1e18;
    for (int i = 1; i < n - 1; i++) {
        ans = min(ans, d1[i] + d2[i]);
    }
    cout << ans << '\n';
}

void setIO(string s) {
    freopen((s + ".in").c_str(), "r", stdin);
    freopen((s + ".out").c_str(), "w", stdout);
}

signed main() {
    ios::sync_with_stdio(false);
    cout.tie(0);
    cin.tie(0);
    //setIO();

    int t = 1;
    if (tc) {
        cin >> t;
    }

    while (t--) {
        solve();
    }
}

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

Main.cpp: In function 'void setIO(std::string)':
Main.cpp:127:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  127 |     freopen((s + ".in").c_str(), "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:128:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  128 |     freopen((s + ".out").c_str(), "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 22
• Subtask 2: 0 / 10
• Subtask 3: 0 / 31
• Subtask 4: 0 / 37