oj.uz

Submission #714681

# Submission time Handle Problem Language Result Execution time Memory
714681 2023-03-25T07:48:13 Z ismayil Stranded Far From Home (BOI22_island) C++17
10 / 100
 1000 ms 524288 KB 
#include <bits/stdc++.h>
#define int long long
//#define endl '\n'
using namespace std;
const int MAX = 2e5 + 5;
vector<int> adj[MAX];
int subtree[MAX], sum[MAX];
int s[MAX], ans[MAX];
void dfs_subtree(int u, int p){
    subtree[u] = s[u];
    for(auto v : adj[u]){
        if(v == p) continue;
        dfs_subtree(v, u);
        subtree[u] += subtree[v];
    }
}
void dfs(int u, int p){
    for(auto v : adj[u]){
        if(v == p) continue;
        if(subtree[v] < s[u]) continue;
        ans[v] = 1;
        dfs(v, u);
    }
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int n, m;
    cin>>n>>m;
    for(int i = 1; i <= n; i++) cin>>s[i];
    for (int i = 1; i <= m; i++)
    {
        int u, v;
        cin>>u>>v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    dfs_subtree(1, 0);
    dfs(1, 0);
    ans[1] = 1;
    for(int i = 1; i <= n; i++){
        cout<<ans[i];
    }
    cout<<endl;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 232 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 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 154 ms 22040 KB Output is correct
4 Correct 119 ms 20748 KB Output is correct
5 Correct 203 ms 16620 KB Output is correct
6 Correct 176 ms 17004 KB Output is correct
7 Correct 170 ms 17020 KB Output is correct
8 Correct 203 ms 17156 KB Output is correct
9 Correct 139 ms 17552 KB Output is correct
10 Correct 81 ms 16080 KB Output is correct
11 Correct 89 ms 17656 KB Output is correct
12 Correct 150 ms 15860 KB Output is correct
13 Correct 139 ms 27124 KB Output is correct
14 Correct 135 ms 27164 KB Output is correct
15 Correct 149 ms 28632 KB Output is correct
16 Correct 117 ms 28356 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Incorrect 150 ms 28476 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

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

Subtask #5
0 / 35.0

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