# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
1101685 | 2024-10-16T15:24:29 Z | pubin06 | Stranded Far From Home (BOI22_island) | C++14 | 13 ms | 6320 KB |
#include <bits/stdc++.h> #define int long long #define fi first #define se second #define sz(v) (int)(v).size() using namespace std; const int MXn = 100005; const long long oo = 1e18; const int MOD = 1e9 + 7; int n, m, a[MXn], s[MXn], par[MXn]; bool cant[MXn]; int find_par(int u) { if (u == par[u]) return u; int r = find_par(par[u]); cant[u] |= cant[par[u]]; return par[u] = r; } signed main(void) { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); #define TASK "" if (ifstream(TASK".INP")) { freopen(TASK".INP", "r", stdin); freopen(TASK".OUT", "w", stdout); } cin >> n >> m; for (int i = 1; i <= n; i++) cin >> a[i], s[i] = a[i]; iota(par + 1, par + 1 + n, 1); vector<array<int, 3>> es; for (int i = 1, u, v; i <= m; i++) { cin >> u >> v; if (a[u] < a[v]) swap(u, v); es.push_back({a[u], u, v}); } sort(begin(es), end(es)); for (auto e: es) { int u = e[1], v = e[2]; u = find_par(u), v = find_par(v); if (u ^ v) { cant[v] = s[v] < a[u]; s[u] += s[v]; par[v] = u; } } for (int i = 1; i <= n; i++) { find_par(i); cout << (cant[i] ? 0 : 1); } return 0; }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 2388 KB | Output is correct |
2 | Correct | 1 ms | 2516 KB | Output is correct |
3 | Correct | 1 ms | 2388 KB | Output is correct |
4 | Correct | 2 ms | 2564 KB | Output is correct |
5 | Correct | 2 ms | 2644 KB | Output is correct |
6 | Correct | 2 ms | 2644 KB | Output is correct |
7 | Correct | 2 ms | 2644 KB | Output is correct |
8 | Correct | 2 ms | 2644 KB | Output is correct |
9 | Correct | 2 ms | 2612 KB | Output is correct |
10 | Correct | 2 ms | 2644 KB | Output is correct |
11 | Correct | 3 ms | 2644 KB | Output is correct |
12 | Correct | 2 ms | 2556 KB | Output is correct |
13 | Correct | 2 ms | 2644 KB | Output is correct |
14 | Correct | 2 ms | 2644 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 2388 KB | Output is correct |
2 | Correct | 1 ms | 2388 KB | Output is correct |
3 | Runtime error | 12 ms | 6320 KB | Execution killed with signal 11 |
4 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 2388 KB | Output is correct |
2 | Runtime error | 13 ms | 6228 KB | Execution killed with signal 11 |
3 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 2388 KB | Output is correct |
2 | Runtime error | 12 ms | 6228 KB | Execution killed with signal 11 |
3 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 2388 KB | Output is correct |
2 | Correct | 1 ms | 2516 KB | Output is correct |
3 | Correct | 1 ms | 2388 KB | Output is correct |
4 | Correct | 2 ms | 2564 KB | Output is correct |
5 | Correct | 2 ms | 2644 KB | Output is correct |
6 | Correct | 2 ms | 2644 KB | Output is correct |
7 | Correct | 2 ms | 2644 KB | Output is correct |
8 | Correct | 2 ms | 2644 KB | Output is correct |
9 | Correct | 2 ms | 2612 KB | Output is correct |
10 | Correct | 2 ms | 2644 KB | Output is correct |
11 | Correct | 3 ms | 2644 KB | Output is correct |
12 | Correct | 2 ms | 2556 KB | Output is correct |
13 | Correct | 2 ms | 2644 KB | Output is correct |
14 | Correct | 2 ms | 2644 KB | Output is correct |
15 | Correct | 1 ms | 2388 KB | Output is correct |
16 | Correct | 1 ms | 2388 KB | Output is correct |
17 | Runtime error | 12 ms | 6320 KB | Execution killed with signal 11 |
18 | Halted | 0 ms | 0 KB | - |