oj.uz

Submission #714719

# Submission time Handle Problem Language Result Execution time Memory
714719 2023-03-25T08:23:25 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 Sub2(int n, int m, vector<ll>&s, vector<ll>&Sum){
    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";

}

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);
    }
    Sub2(n, m, s, Sum);




}


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 231 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 1 ms 256 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 178 ms 21584 KB Output is correct
4 Correct 166 ms 21544 KB Output is correct
5 Correct 223 ms 14900 KB Output is correct
6 Correct 234 ms 15348 KB Output is correct
7 Correct 212 ms 15448 KB Output is correct
8 Correct 215 ms 15472 KB Output is correct
9 Correct 132 ms 15292 KB Output is correct
10 Correct 110 ms 16160 KB Output is correct
11 Correct 109 ms 16084 KB Output is correct
12 Correct 172 ms 15436 KB Output is correct
13 Correct 133 ms 30944 KB Output is correct
14 Correct 151 ms 30956 KB Output is correct
15 Correct 153 ms 30944 KB Output is correct
16 Correct 88 ms 30644 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 160 ms 30792 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 331036 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

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