oj.uz

Submission #592974

# Submission time Handle Problem Language Result Execution time Memory
592974 2022-07-10T02:53:32 Z 1zaid1 Stranded Far From Home (BOI22_island) C++17
20 / 100
 282 ms 62392 KB 
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
const int M = 4e5+1;
#define int long long
vector<int> node[M], v[M];
bitset<200005> vis;
int p[M], n, cnt[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++) 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;
}

void dfs(int s) {
    cnt[s] = p[s];
    vis[s] = true;
    v[s].push_back(s);
    for (int i:node[s]) {
        if (!vis[i]) {
            dfs(i);
            if (cnt[i] >= p[s]) {
                if (v[i].size() > v[s].size()) swap(v[s], v[i]);
                for (int j:v[i]) v[s].push_back(j);
            }

            cnt[s] += cnt[i];
        }
    }
}
 
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);
    }
 
    if (n <= 2000) {
        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;
    } else {
        dfs(1);
        bitset<200005> bt;
        for (int i:v[1]) bt[i] = 1;
        for (int i = 1; i <= n; i++) cout << bt[i]; cout << endl;
    }
 
    return 0;
}
/*
4 3
4 2 2 1
1 2
3 2
4 1
*/

Compilation message

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

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 19028 KB Output is correct
2 Correct 9 ms 19028 KB Output is correct
3 Correct 9 ms 19072 KB Output is correct
4 Correct 163 ms 19240 KB Output is correct
5 Correct 146 ms 19236 KB Output is correct
6 Correct 168 ms 19240 KB Output is correct
7 Correct 145 ms 19152 KB Output is correct
8 Correct 108 ms 19244 KB Output is correct
9 Correct 218 ms 19276 KB Output is correct
10 Correct 63 ms 19236 KB Output is correct
11 Correct 62 ms 19192 KB Output is correct
12 Correct 63 ms 19280 KB Output is correct
13 Correct 103 ms 19240 KB Output is correct
14 Correct 82 ms 19156 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 19028 KB Output is correct
2 Correct 10 ms 19068 KB Output is correct
3 Correct 180 ms 48820 KB Output is correct
4 Correct 174 ms 48632 KB Output is correct
5 Correct 202 ms 40732 KB Output is correct
6 Correct 234 ms 41968 KB Output is correct
7 Correct 235 ms 42860 KB Output is correct
8 Correct 282 ms 46352 KB Output is correct
9 Correct 177 ms 44552 KB Output is correct
10 Correct 131 ms 39596 KB Output is correct
11 Correct 150 ms 40928 KB Output is correct
12 Correct 201 ms 41148 KB Output is correct
13 Correct 151 ms 60168 KB Output is correct
14 Correct 160 ms 61252 KB Output is correct
15 Correct 167 ms 62392 KB Output is correct
16 Correct 106 ms 61060 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 19028 KB Output is correct
2 Incorrect 187 ms 60840 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 19156 KB Output is correct
2 Incorrect 233 ms 43264 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 19028 KB Output is correct
2 Correct 9 ms 19028 KB Output is correct
3 Correct 9 ms 19072 KB Output is correct
4 Correct 163 ms 19240 KB Output is correct
5 Correct 146 ms 19236 KB Output is correct
6 Correct 168 ms 19240 KB Output is correct
7 Correct 145 ms 19152 KB Output is correct
8 Correct 108 ms 19244 KB Output is correct
9 Correct 218 ms 19276 KB Output is correct
10 Correct 63 ms 19236 KB Output is correct
11 Correct 62 ms 19192 KB Output is correct
12 Correct 63 ms 19280 KB Output is correct
13 Correct 103 ms 19240 KB Output is correct
14 Correct 82 ms 19156 KB Output is correct
15 Correct 10 ms 19028 KB Output is correct
16 Correct 10 ms 19068 KB Output is correct
17 Correct 180 ms 48820 KB Output is correct
18 Correct 174 ms 48632 KB Output is correct
19 Correct 202 ms 40732 KB Output is correct
20 Correct 234 ms 41968 KB Output is correct
21 Correct 235 ms 42860 KB Output is correct
22 Correct 282 ms 46352 KB Output is correct
23 Correct 177 ms 44552 KB Output is correct
24 Correct 131 ms 39596 KB Output is correct
25 Correct 150 ms 40928 KB Output is correct
26 Correct 201 ms 41148 KB Output is correct
27 Correct 151 ms 60168 KB Output is correct
28 Correct 160 ms 61252 KB Output is correct
29 Correct 167 ms 62392 KB Output is correct
30 Correct 106 ms 61060 KB Output is correct
31 Correct 12 ms 19028 KB Output is correct
32 Incorrect 187 ms 60840 KB Output isn't correct
33 Halted 0 ms 0 KB -