oj.uz

Submission #640463

# Submission time Handle Problem Language Result Execution time Memory
640463 2022-09-14T17:45:39 Z makanhulia Stranded Far From Home (BOI22_island) C++17
10 / 100
 232 ms 52332 KB 
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define ii pair<int,int>
using namespace std;

const int dv = 1e9 + 7;
const int sz = 1e5;

int n, m, vtd[2*sz+5], p[2*sz+5], idx, trav;

vector<int> adj[2*sz+5], v[2*sz+5];
ll cnt[2*sz+5];

void dfs(int node) {
    cnt[node] = p[node];
    vtd[node] = 1;
    v[node].push_back(node);
    for(auto i : adj[node]) {
        if(!vtd[i]) {
            dfs(i);
            if(cnt[i] >= p[node]) {
                if(v[i].size() > v[node].size()) swap(v[node], v[i]);
                for(int j : v[i]) v[node].push_back(j);
            }
            cnt[node] += cnt[i];
        }
    }
}

int ans[2*sz+5];

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> m;
    for(int i = 1; i <= n ;++i) {
        cin >> p[i];
    }
    for(int i = 0; i < m; ++i) {
        int a, b; cin >> a >> b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    dfs(1);
    for(auto i: v[1]) ans[i] = 1;
    for(int i = 1; i <= n; ++i) cout << ans[i];
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9728 KB Output is correct
2 Correct 7 ms 9684 KB Output is correct
3 Correct 7 ms 9684 KB Output is correct
4 Incorrect 7 ms 9996 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9728 KB Output is correct
2 Correct 5 ms 9728 KB Output is correct
3 Correct 163 ms 38936 KB Output is correct
4 Correct 158 ms 37512 KB Output is correct
5 Correct 215 ms 30980 KB Output is correct
6 Correct 210 ms 31628 KB Output is correct
7 Correct 232 ms 31572 KB Output is correct
8 Correct 213 ms 33400 KB Output is correct
9 Correct 157 ms 31516 KB Output is correct
10 Correct 134 ms 29008 KB Output is correct
11 Correct 132 ms 30324 KB Output is correct
12 Correct 212 ms 29240 KB Output is correct
13 Correct 172 ms 50392 KB Output is correct
14 Correct 146 ms 50640 KB Output is correct
15 Correct 158 ms 52332 KB Output is correct
16 Correct 103 ms 51552 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Incorrect 160 ms 52032 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9684 KB Output is correct
2 Incorrect 226 ms 32964 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9728 KB Output is correct
2 Correct 7 ms 9684 KB Output is correct
3 Correct 7 ms 9684 KB Output is correct
4 Incorrect 7 ms 9996 KB Output isn't correct
5 Halted 0 ms 0 KB -