Submission #882727

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
882727	2023-12-03T14:41:28 Z	tsumondai	Airplane (NOI23_airplane)	C++14	100 / 100	414 ms	53964 KB

Main

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

#define int long long
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define foru(i, l, r) for(int i = l; i <= r; i++)
#define ford(i, r, l) for(int i = r; i >= l; i--)
#define __TIME  (1.0 * clock() / CLOCKS_PER_SEC)

typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;

const int N = 1e6 + 5;

const int oo = 1e18, mod = 1e9 + 7;

int n, m, k, h[N];
string s;
vector<int> adj[N];

int dist[N][2];

void dijkstra(int s, int source) {
    foru(i, 0, n + 1) dist[i][source] = oo;
    priority_queue <pair <long long, int>> pq;
    pq.push(make_pair(dist[s][source] = 0, s));
    while (!pq.empty()) {
        pair<long long, long long> tmp = pq.top(); pq.pop();
        long long du = tmp.first, u = tmp.second;
        du = -du;
        if (du != dist[u][source]) continue;
        for (int v : adj[u]) if (dist[v][source] > max(h[v], dist[u][source] + 1)) {
                dist[v][source] = max(h[v], dist[u][source] + 1);
                pq.push(make_pair(-dist[v][source], v));
            }
    }
}

void process() {
    // 0: from 1
    // 1: from n
    cin >> n >> m;
    foru(i, 1, n) cin >> h[i];
    foru(i, 1, m) {
        int u, v; cin >> u >> v;
        adj[u].pb(v);
        adj[v].pb(u);
    }

    dijkstra(1, 0);
    dijkstra(n, 1);
    int ans = oo;

    foru(u, 1, n) {
        ans = min(ans, max(dist[u][0], dist[u][1]) * 2);
        for (int v : adj[u]) {
            ans = min(ans, max(dist[v][0], dist[u][1]) * 2 + 1);
            ans = min(ans, max(dist[u][0], dist[v][1]) * 2 + 1);
        }
    }
    cout << ans;
    return;
}

signed main() {
    cin.tie(0)->sync_with_stdio(false);
    //freopen(".inp", "r", stdin);
    //freopen(".out", "w", stdout);
    process();
    cerr << "Time elapsed: " << __TIME << " s.\n";
    return 0;
}

/*
Xét các trường hợp đặc biệt
Kiểm tra lại input/output
Cố gắng trâu
Lật ngược bài toán
Keep calm and get VOI
Flow:

*/

Subtask #1
22.0 / 22.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	6 ms	25052 KB	Output is correct
2	Correct	66 ms	40760 KB	Output is correct
3	Correct	63 ms	41252 KB	Output is correct
4	Correct	67 ms	41288 KB	Output is correct
5	Correct	71 ms	41824 KB	Output is correct
6	Correct	68 ms	41788 KB	Output is correct
7	Correct	69 ms	41812 KB	Output is correct
8	Correct	5 ms	24924 KB	Output is correct

Subtask #2
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	25040 KB	Output is correct
2	Correct	6 ms	25040 KB	Output is correct
3	Correct	6 ms	24924 KB	Output is correct
4	Correct	6 ms	25092 KB	Output is correct
5	Correct	5 ms	24924 KB	Output is correct
6	Correct	7 ms	25180 KB	Output is correct
7	Correct	8 ms	25180 KB	Output is correct
8	Correct	7 ms	25180 KB	Output is correct
9	Correct	6 ms	25180 KB	Output is correct
10	Correct	7 ms	25012 KB	Output is correct
11	Correct	7 ms	25180 KB	Output is correct
12	Correct	7 ms	25032 KB	Output is correct
13	Correct	6 ms	25180 KB	Output is correct
14	Correct	7 ms	25108 KB	Output is correct
15	Correct	8 ms	25108 KB	Output is correct
16	Correct	9 ms	25176 KB	Output is correct
17	Correct	8 ms	25100 KB	Output is correct
18	Correct	6 ms	24924 KB	Output is correct

Subtask #3
31.0 / 31.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	25040 KB	Output is correct
2	Correct	6 ms	25040 KB	Output is correct
3	Correct	6 ms	24924 KB	Output is correct
4	Correct	6 ms	25092 KB	Output is correct
5	Correct	5 ms	24924 KB	Output is correct
6	Correct	7 ms	25180 KB	Output is correct
7	Correct	8 ms	25180 KB	Output is correct
8	Correct	7 ms	25180 KB	Output is correct
9	Correct	6 ms	25180 KB	Output is correct
10	Correct	7 ms	25012 KB	Output is correct
11	Correct	7 ms	25180 KB	Output is correct
12	Correct	7 ms	25032 KB	Output is correct
13	Correct	6 ms	25180 KB	Output is correct
14	Correct	7 ms	25108 KB	Output is correct
15	Correct	8 ms	25108 KB	Output is correct
16	Correct	9 ms	25176 KB	Output is correct
17	Correct	8 ms	25100 KB	Output is correct
18	Correct	6 ms	24924 KB	Output is correct
19	Correct	7 ms	25180 KB	Output is correct
20	Correct	6 ms	25176 KB	Output is correct
21	Correct	7 ms	25176 KB	Output is correct
22	Correct	6 ms	25180 KB	Output is correct
23	Correct	6 ms	25180 KB	Output is correct
24	Correct	7 ms	25428 KB	Output is correct
25	Correct	7 ms	25180 KB	Output is correct
26	Correct	7 ms	25180 KB	Output is correct
27	Correct	7 ms	25264 KB	Output is correct
28	Correct	7 ms	25180 KB	Output is correct
29	Correct	8 ms	25180 KB	Output is correct
30	Correct	8 ms	25356 KB	Output is correct

Subtask #4
37.0 / 37.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	6 ms	25052 KB	Output is correct
2	Correct	66 ms	40760 KB	Output is correct
3	Correct	63 ms	41252 KB	Output is correct
4	Correct	67 ms	41288 KB	Output is correct
5	Correct	71 ms	41824 KB	Output is correct
6	Correct	68 ms	41788 KB	Output is correct
7	Correct	69 ms	41812 KB	Output is correct
8	Correct	5 ms	24924 KB	Output is correct
9	Correct	5 ms	25040 KB	Output is correct
10	Correct	6 ms	25040 KB	Output is correct
11	Correct	6 ms	24924 KB	Output is correct
12	Correct	6 ms	25092 KB	Output is correct
13	Correct	5 ms	24924 KB	Output is correct
14	Correct	7 ms	25180 KB	Output is correct
15	Correct	8 ms	25180 KB	Output is correct
16	Correct	7 ms	25180 KB	Output is correct
17	Correct	6 ms	25180 KB	Output is correct
18	Correct	7 ms	25012 KB	Output is correct
19	Correct	7 ms	25180 KB	Output is correct
20	Correct	7 ms	25032 KB	Output is correct
21	Correct	6 ms	25180 KB	Output is correct
22	Correct	7 ms	25108 KB	Output is correct
23	Correct	8 ms	25108 KB	Output is correct
24	Correct	9 ms	25176 KB	Output is correct
25	Correct	8 ms	25100 KB	Output is correct
26	Correct	6 ms	24924 KB	Output is correct
27	Correct	7 ms	25180 KB	Output is correct
28	Correct	6 ms	25176 KB	Output is correct
29	Correct	7 ms	25176 KB	Output is correct
30	Correct	6 ms	25180 KB	Output is correct
31	Correct	6 ms	25180 KB	Output is correct
32	Correct	7 ms	25428 KB	Output is correct
33	Correct	7 ms	25180 KB	Output is correct
34	Correct	7 ms	25180 KB	Output is correct
35	Correct	7 ms	25264 KB	Output is correct
36	Correct	7 ms	25180 KB	Output is correct
37	Correct	8 ms	25180 KB	Output is correct
38	Correct	8 ms	25356 KB	Output is correct
39	Correct	166 ms	42924 KB	Output is correct
40	Correct	119 ms	42152 KB	Output is correct
41	Correct	134 ms	42004 KB	Output is correct
42	Correct	119 ms	42084 KB	Output is correct
43	Correct	161 ms	42184 KB	Output is correct
44	Correct	146 ms	42156 KB	Output is correct
45	Correct	125 ms	42008 KB	Output is correct
46	Correct	128 ms	42044 KB	Output is correct
47	Correct	155 ms	42156 KB	Output is correct
48	Correct	128 ms	42100 KB	Output is correct
49	Correct	167 ms	42860 KB	Output is correct
50	Correct	202 ms	42552 KB	Output is correct
51	Correct	208 ms	42784 KB	Output is correct
52	Correct	264 ms	48704 KB	Output is correct
53	Correct	246 ms	47520 KB	Output is correct
54	Correct	240 ms	47712 KB	Output is correct
55	Correct	296 ms	47920 KB	Output is correct
56	Correct	369 ms	53072 KB	Output is correct
57	Correct	414 ms	53036 KB	Output is correct
58	Correct	367 ms	53964 KB	Output is correct
59	Correct	366 ms	53964 KB	Output is correct
60	Correct	302 ms	53756 KB	Output is correct
61	Correct	356 ms	53448 KB	Output is correct
62	Correct	254 ms	52744 KB	Output is correct
63	Correct	349 ms	52680 KB	Output is correct
64	Correct	339 ms	52788 KB	Output is correct
65	Correct	347 ms	53580 KB	Output is correct
66	Correct	283 ms	52688 KB	Output is correct
67	Correct	335 ms	53080 KB	Output is correct

Submission #882727

Compilation message

Subtask #1 22.0 / 22.0

Subtask #2 10.0 / 10.0

Subtask #3 31.0 / 31.0

Subtask #4 37.0 / 37.0

Subtask #1
22.0 / 22.0

Subtask #2
10.0 / 10.0

Subtask #3
31.0 / 31.0

Subtask #4
37.0 / 37.0