# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
614240 | 2022-07-30T23:08:43 Z | Plurm | Stranded Far From Home (BOI22_island) | C++11 | 1000 ms | 15668 KB |
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> using namespace __gnu_pbds; using namespace std; int s[200005]; vector<int> g[200005]; int n, m; bool check(int u) { priority_queue<pair<int, int>> pq; long long allies = s[u]; gp_hash_table<int, null_type> alliance; alliance.insert(u); for (int v : g[u]) pq.push({-s[v], v}); while (!pq.empty()) { int vnxt = pq.top().second; pq.pop(); if (alliance.find(vnxt) != alliance.end()) continue; if (s[vnxt] <= allies) { allies += 1ll * s[vnxt]; alliance.insert(vnxt); for (int v : g[vnxt]) { if (alliance.find(v) == alliance.end()) { pq.push({-s[v], v}); } } } else { return false; } } return true; } int par[200005]; long long qs[200005]; int suff[200005]; bool dp[200005]; int main() { scanf("%d%d", &n, &m); for (int i = 1; i <= n; i++) { scanf("%d", s + i); qs[i] = qs[i - 1] + s[i]; } for (int i = 0; i < m; i++) { int u, v; scanf("%d%d", &u, &v); g[u].push_back(v); g[v].push_back(u); } if (n > 2000) { suff[n + 1] = n + 1; for (int i = n; i > 0; i--) { par[i] = i; for (int j : g[i]) { if (j < i) par[i] = min(par[i], j); } suff[i] = min(suff[i + 1], par[i]); } dp[1] = true; for (int i = 2; i <= n; i++) { dp[i] = (qs[n] - qs[i - 1]) >= s[i - 1] ? dp[i - 1] : false; } for (int i = 1; i <= n; i++) { int x = suff[i]; while (suff[x] < x) x = suff[x]; if (dp[x]) printf("1"); else printf("0"); } printf("\n"); } else { for (int i = 1; i <= n; i++) { if (check(i)) printf("1"); else printf("0"); } printf("\n"); } return 0; }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 4948 KB | Output is correct |
2 | Correct | 3 ms | 4948 KB | Output is correct |
3 | Correct | 2 ms | 5068 KB | Output is correct |
4 | Correct | 253 ms | 5144 KB | Output is correct |
5 | Correct | 215 ms | 5156 KB | Output is correct |
6 | Correct | 373 ms | 5144 KB | Output is correct |
7 | Correct | 260 ms | 5076 KB | Output is correct |
8 | Correct | 194 ms | 5152 KB | Output is correct |
9 | Correct | 279 ms | 5148 KB | Output is correct |
10 | Correct | 112 ms | 5156 KB | Output is correct |
11 | Correct | 95 ms | 5156 KB | Output is correct |
12 | Correct | 156 ms | 5152 KB | Output is correct |
13 | Correct | 188 ms | 5152 KB | Output is correct |
14 | Correct | 143 ms | 5156 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 4948 KB | Output is correct |
2 | Correct | 2 ms | 4948 KB | Output is correct |
3 | Execution timed out | 1086 ms | 15668 KB | Time limit exceeded |
4 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 4948 KB | Output is correct |
2 | Execution timed out | 1096 ms | 15456 KB | Time limit exceeded |
3 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 4948 KB | Output is correct |
2 | Incorrect | 126 ms | 15548 KB | Output isn't correct |
3 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 4948 KB | Output is correct |
2 | Correct | 3 ms | 4948 KB | Output is correct |
3 | Correct | 2 ms | 5068 KB | Output is correct |
4 | Correct | 253 ms | 5144 KB | Output is correct |
5 | Correct | 215 ms | 5156 KB | Output is correct |
6 | Correct | 373 ms | 5144 KB | Output is correct |
7 | Correct | 260 ms | 5076 KB | Output is correct |
8 | Correct | 194 ms | 5152 KB | Output is correct |
9 | Correct | 279 ms | 5148 KB | Output is correct |
10 | Correct | 112 ms | 5156 KB | Output is correct |
11 | Correct | 95 ms | 5156 KB | Output is correct |
12 | Correct | 156 ms | 5152 KB | Output is correct |
13 | Correct | 188 ms | 5152 KB | Output is correct |
14 | Correct | 143 ms | 5156 KB | Output is correct |
15 | Correct | 3 ms | 4948 KB | Output is correct |
16 | Correct | 2 ms | 4948 KB | Output is correct |
17 | Execution timed out | 1086 ms | 15668 KB | Time limit exceeded |
18 | Halted | 0 ms | 0 KB | - |