QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #834972 | #6391. Airplane | AdamGS | 0 | 43ms | 16544kb | C++23 | 918b | 2024-12-28 08:34:52 | 2024-12-28 08:35:00 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const int LIM=2e5+7, INF=1e9+7;
vector<int>V[LIM];
int T[LIM], n;
vector<int>solve(int x) {
vector<int>odl(n, INF);
priority_queue<pair<int,int>>q;
q.push({0, x});
while(!q.empty()) {
int o=-q.top().st, p=q.top().nd; q.pop();
if(odl[p]<=o) continue;
odl[p]=o;
for(auto i : V[p]) q.push({-max(o+1, T[i]), i});
}
return odl;
}
int main() {
ios_base::sync_with_stdio(0); cin.tie(0);
int m;
cin >> n >> m;
rep(i, n) cin >> T[i];
rep(i, m) {
int a, b;
cin >> a >> b; --a; --b;
V[a].pb(b);
V[b].pb(a);
}
vector<int>A=solve(0);
vector<int>B=solve(n-1);
int ans=INF;
rep(i, n) ans=min(ans, max(2*T[i], 2*max(A[i], B[i])-1));
cout << ans << '\n';
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 0
Wrong Answer
time: 43ms
memory: 16544kb
input:
200000 199999 0 199 58 60 83 5 10 182 87 65 104 153 197 137 80 143 34 181 62 48 10 57 86 58 117 10 171 188 95 52 95 140 126 0 196 85 87 14 10 139 177 92 31 18 102 146 68 9 91 124 156 38 41 121 183 10 32 174 171 29 49 26 118 1 69 185 57 168 54 159 195 95 9 32 195 70 85 174 158 82 33 197 66 189 198 11...
output:
200377
result:
wrong answer 1st lines differ - expected: '200378', found: '200377'
Subtask #2:
score: 0
Wrong Answer
Test #8:
score: 10
Accepted
time: 1ms
memory: 3852kb
input:
6 10 0 0 6 1 8 0 5 6 2 3 5 4 6 4 3 5 6 2 3 6 3 4 3 1 6 1
output:
1
result:
ok single line: '1'
Test #9:
score: 10
Accepted
time: 1ms
memory: 3728kb
input:
4 5 0 1 2 0 2 4 1 2 3 2 4 1 4 3
output:
1
result:
ok single line: '1'
Test #10:
score: 10
Accepted
time: 1ms
memory: 3560kb
input:
20 40 0 2 1 5 3 4 1 5 3 2 5 5 5 3 3 4 4 3 4 0 4 3 15 18 11 18 10 13 1 3 9 14 16 14 16 1 5 3 13 15 20 7 20 16 9 11 16 11 1 2 6 2 19 10 7 13 15 10 7 15 8 11 5 9 8 12 6 7 7 14 2 18 17 16 8 3 1 10 5 2 4 2 11 13 17 3 11 5 4 8 13 6 17 1 10 7 5 6 13 9
output:
4
result:
ok single line: '4'
Test #11:
score: 10
Accepted
time: 2ms
memory: 3696kb
input:
2000 2000 0 1990 1247 1110 1102 1411 1445 1492 1349 1302 1404 1541 1660 1333 1461 1710 1655 1489 1310 1660 1141 1069 1167 1020 1564 1746 1354 1607 1144 1636 1901 1099 1167 1112 1001 1210 1126 1537 1082 1814 1469 1884 1375 1703 1393 1335 1194 1444 1895 1933 1038 1357 1405 1039 1804 1958 1642 1418 169...
output:
4027
result:
ok single line: '4027'
Test #12:
score: 0
Wrong Answer
time: 2ms
memory: 3748kb
input:
2000 2000 0 53 12 10 76 82 78 52 30 63 13 87 53 19 51 80 25 82 8 75 12 19 5 49 9 28 5 51 65 9 50 57 9 95 39 33 12 94 26 83 76 82 15 99 39 27 95 13 48 23 58 86 96 100 19 84 93 13 69 61 20 25 23 74 19 12 5 108 16 67 50 16 51 106 79 107 42 39 105 79 17 22 30 28 84 25 80 36 87 22 82 107 31 77 103 96 70 ...
output:
271
result:
wrong answer 1st lines differ - expected: '272', found: '271'
Subtask #3:
score: 0
Skipped
Dependency #2:
0%
Subtask #4:
score: 0
Skipped
Dependency #1:
0%