oj.uz

Submission #592037

# Submission time Handle Problem Language Result Execution time Memory
592037 2022-07-08T12:10:30 Z 1zaid1 Stranded Far From Home (BOI22_island) C++17
10 / 100
 1000 ms 20744 KB 
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
const int M = 4e5+1;
#define int long long
vector<int> node[M];
bitset<200005> vis;
int p[M], n, d[M];

struct in{int a;};
bool operator<(in a, in b) {return p[a.a] > p[b.a];}
bool bfs(int s) {
    for (int i = 1; i <= n; i++) d[i] = vis[i] = 0;
    int sum = 0;
    priority_queue<in> q;
    vis[s] = 1;
    q.push({s});
    while (!q.empty()) {
        auto [t] = q.top(); q.pop();
        if (t != s && p[t] > sum) {
            return 0;
        } else sum += p[t];
        for (int i:node[t]) {
            if (!vis[i]) {
                vis[i] = 1;
                q.push({i});
            }
        }
    }
 
    return true;
}
 
signed main() {
    cin.tie(0)->sync_with_stdio(0);
 
    int m;
    cin >> n >> m;
 
    for (int i = 1; i <= n; i++) cin >> p[i];
    for (int i = 1; i <= m; i++) {
        int a, b;
        cin >> a >> b;
 
        node[a].push_back(b);
        node[b].push_back(a);
    }
 
    for (int i = 1; i <= n; i++) sort(node[i].begin(), node[i].end(),[](int a, int b) {return p[a] < p[b];});
    for (int i = 1; i <= n; i++) cout << bfs(i); cout << endl;
 
    return 0;
}
/*
b 
4 3
4 2 2 1
1 2
3 2
4 1
*/

Compilation message

island.cpp: In function 'int main()':
island.cpp:50:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   50 |     for (int i = 1; i <= n; i++) cout << bfs(i); cout << endl;
      |     ^~~
island.cpp:50:50: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   50 |     for (int i = 1; i <= n; i++) cout << bfs(i); cout << endl;
      |                                                  ^~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 4 ms 9684 KB Output is correct
3 Correct 6 ms 9684 KB Output is correct
4 Correct 163 ms 9824 KB Output is correct
5 Correct 145 ms 9852 KB Output is correct
6 Correct 161 ms 9852 KB Output is correct
7 Correct 149 ms 9844 KB Output is correct
8 Correct 112 ms 9832 KB Output is correct
9 Correct 215 ms 9864 KB Output is correct
10 Correct 60 ms 9844 KB Output is correct
11 Correct 59 ms 9860 KB Output is correct
12 Correct 60 ms 9872 KB Output is correct
13 Correct 95 ms 9832 KB Output is correct
14 Correct 79 ms 9812 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9608 KB Output is correct
2 Correct 5 ms 9672 KB Output is correct
3 Execution timed out 1084 ms 20744 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Execution timed out 1091 ms 19064 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Execution timed out 1090 ms 20240 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 4 ms 9684 KB Output is correct
3 Correct 6 ms 9684 KB Output is correct
4 Correct 163 ms 9824 KB Output is correct
5 Correct 145 ms 9852 KB Output is correct
6 Correct 161 ms 9852 KB Output is correct
7 Correct 149 ms 9844 KB Output is correct
8 Correct 112 ms 9832 KB Output is correct
9 Correct 215 ms 9864 KB Output is correct
10 Correct 60 ms 9844 KB Output is correct
11 Correct 59 ms 9860 KB Output is correct
12 Correct 60 ms 9872 KB Output is correct
13 Correct 95 ms 9832 KB Output is correct
14 Correct 79 ms 9812 KB Output is correct
15 Correct 5 ms 9608 KB Output is correct
16 Correct 5 ms 9672 KB Output is correct
17 Execution timed out 1084 ms 20744 KB Time limit exceeded
18 Halted 0 ms 0 KB -