oj.uz

Submission #714714

# Submission time Handle Problem Language Result Execution time Memory
714714 2023-03-25T08:20:43 Z murad_2005 Stranded Far From Home (BOI22_island) C++14
10 / 100
 1000 ms 524288 KB 
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define ld long double
#define pb push_back
#define pf push_front
#define pii pair<int, int>
#define pllll pair<ll, ll>
#define size(v) v.size()
#define all(v) v.begin(), v.end()
#define INF 2e9
#define f first
#define s second

using namespace std;

vector<vector<int>>g;
vector<ll>Sum;

void dfs(int node, int par, vector<ll>&s){
    for(int to : g[node]){
        if(to != par){
            dfs(to, node, s);
            Sum[node] += Sum[to];
        }
    }
    Sum[node] += s[node];
}

void DFS(int node, int par, vector<ll>&s, vector<int>&isOkay){
    for(int to : g[node]){
        if(to != par){
            if(!isOkay[node]){
                isOkay[to] = 0;
            }else{
                if(Sum[to] >= s[node]){
                    isOkay[to] = 1;
                }
            }
            DFS(to, node, s, isOkay);
        }
    }
}

void solve(){
    int n, m;
    cin >> n >> m;
    vector<ll>s(n + 1);
    g.resize(n + 1);
    Sum.assign(n + 1, 0);
    for(int i = 1; i <= n; ++i){
        cin >> s[i];
    }
    for(int i = 1; i <= m; ++i){
        int u, v;
        cin >> u >> v;
        g[u].pb(v);
        g[v].pb(u);
    }
    vector<int>isOkay(n + 1, 0);
    isOkay[1] = 1;
    dfs(1, 1, s);
    DFS(1, 1, s, isOkay);
    for(int i = 1; i <= n; ++i){
        cout << isOkay[i];
    }
    cout << "\n";



}


int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t;
    // cin >> t;
    t = 1;
    while(t--){
        solve();
    }
    return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 225 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 142 ms 21584 KB Output is correct
4 Correct 140 ms 21580 KB Output is correct
5 Correct 158 ms 15108 KB Output is correct
6 Correct 159 ms 15436 KB Output is correct
7 Correct 197 ms 15448 KB Output is correct
8 Correct 185 ms 15436 KB Output is correct
9 Correct 133 ms 15320 KB Output is correct
10 Correct 96 ms 16064 KB Output is correct
11 Correct 93 ms 16080 KB Output is correct
12 Correct 154 ms 15540 KB Output is correct
13 Correct 141 ms 30968 KB Output is correct
14 Correct 143 ms 30988 KB Output is correct
15 Correct 142 ms 31036 KB Output is correct
16 Correct 88 ms 30676 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 148 ms 30788 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

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

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Runtime error 225 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -