oj.uz

Submission #714816

# Submission time Handle Problem Language Result Execution time Memory
714816 2023-03-25T10:01:29 Z Nelt Stranded Far From Home (BOI22_island) C++17
20 / 100
 1000 ms 178368 KB 
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,avx2,fma")

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

/* DEFINES */
#define F first
#define S second
#define ll long long
#define ull unsigned long long
#define ld long double
#define npos ULLONG_MAX
#define INF LLONG_MAX
#define vv(a) vector<a>
#define pp(a, b) pair<a, b>
#define pq(a) priority_queue<a>
#define qq(a) queue<a>
#define ss(a) set<a>
#define mm(a, b) map<a, b>
#define ump(a, b) unordered_map<a, b>
#define sync                      \
    ios_base::sync_with_stdio(0); \
    cin.tie(0);                   \
    cout.tie(0);
#define elif else if
#define endl "\n"
#define allc(a) begin(a), end(a)
#define all(a) a, a + sizeof(a) / sizeof(a[0])
#define pb push_back
#define logi(a) __lg(a)
#define sqrt(a) sqrtl(a)
#define mpr make_pair
#define ins insert
using namespace std;
using namespace __gnu_pbds;
using namespace __cxx11;
typedef char chr;
typedef basic_string<chr> str;
template <typename T, typename key = less<T>>
using ordered_set = tree<T, null_type, key, rb_tree_tag, tree_order_statistics_node_update>;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
const ll N = 2e5 + 5;
vv(ll) g[N];
ll a[N], sub[N];
ll ans[N];
void dfs(ll v, ll par = 0)
{
    sub[v] = a[v];
    for (ll to : g[v])
        if (to != par)
            dfs(to, v), sub[v] += sub[to];
}
void dfs1(ll v, ll par = 0)
{
    ans[v] = ans[par] and sub[v] >= a[par];
    for (ll to : g[v])
        if (to != par)
            dfs1(to, v);
}
void solve()
{
    ans[0] = 1;
    ll n, m;
    cin >> n >> m;
    for (ll i = 1; i <= n; i++)
        cin >> a[i];
    while (m--)
    {
        ll x, y;
        cin >> x >> y;
        g[x].pb(y);
        g[y].pb(x);
    }
    if (n <= 2010)
    {
        ss(pp(ll, ll)) s;
        bool us[n + 1];
        for (ll i = 1; i <= n; i++)
        {
            memset(us, 0, sizeof(us));
            s.clear();
            for (ll j : g[i])
                s.ins(mpr(a[j], j));
            us[i] = 1;
            ll val = a[i];
            while (!s.empty() and s.begin()->F <= val)
            {
                auto tmp = *s.begin();
                us[tmp.S] = 1;
                val += tmp.F;
                for (ll to : g[tmp.S])
                    if (!us[to])
                        s.ins(mpr(a[to], to));
                s.erase(tmp);
            }
            if (count(us + 1, us + n + 1, 0))
                cout << "0";
            else
                cout << "1";
        }
        cout << endl;
        return;
    }
    dfs(1);
    dfs1(1);
    for (ll i = 1; i <= n; i++)
        cout << ans[i];
    cout << endl;
}
/*

*/
int main()
{
    sync
        // precomp();
        ll t = 1;
    // cin >> t;
    for (ll i = 1; i <= t; i++)
        // cout << "Case " << i << ": ",
        solve();
    cerr << "\nTime elapsed : " << clock() * 1000.0 / CLOCKS_PER_SEC << " ms\n";
}

Subtask #1
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 3 ms 4948 KB Output is correct
4 Correct 287 ms 5136 KB Output is correct
5 Correct 291 ms 5108 KB Output is correct
6 Correct 432 ms 5136 KB Output is correct
7 Correct 305 ms 5076 KB Output is correct
8 Correct 214 ms 5076 KB Output is correct
9 Correct 451 ms 5172 KB Output is correct
10 Correct 159 ms 5196 KB Output is correct
11 Correct 156 ms 5096 KB Output is correct
12 Correct 164 ms 5132 KB Output is correct
13 Correct 264 ms 5076 KB Output is correct
14 Correct 160 ms 5104 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 164 ms 19576 KB Output is correct
4 Correct 138 ms 19504 KB Output is correct
5 Correct 213 ms 16752 KB Output is correct
6 Correct 197 ms 17124 KB Output is correct
7 Correct 181 ms 17104 KB Output is correct
8 Correct 176 ms 17196 KB Output is correct
9 Correct 181 ms 18392 KB Output is correct
10 Correct 94 ms 17808 KB Output is correct
11 Correct 101 ms 17648 KB Output is correct
12 Correct 177 ms 17160 KB Output is correct
13 Correct 148 ms 22064 KB Output is correct
14 Correct 143 ms 21960 KB Output is correct
15 Correct 143 ms 22068 KB Output is correct
16 Correct 84 ms 21820 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 143 ms 21900 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

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

Subtask #5
0 / 35.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 3 ms 4948 KB Output is correct
4 Correct 287 ms 5136 KB Output is correct
5 Correct 291 ms 5108 KB Output is correct
6 Correct 432 ms 5136 KB Output is correct
7 Correct 305 ms 5076 KB Output is correct
8 Correct 214 ms 5076 KB Output is correct
9 Correct 451 ms 5172 KB Output is correct
10 Correct 159 ms 5196 KB Output is correct
11 Correct 156 ms 5096 KB Output is correct
12 Correct 164 ms 5132 KB Output is correct
13 Correct 264 ms 5076 KB Output is correct
14 Correct 160 ms 5104 KB Output is correct
15 Correct 4 ms 4948 KB Output is correct
16 Correct 3 ms 4948 KB Output is correct
17 Correct 164 ms 19576 KB Output is correct
18 Correct 138 ms 19504 KB Output is correct
19 Correct 213 ms 16752 KB Output is correct
20 Correct 197 ms 17124 KB Output is correct
21 Correct 181 ms 17104 KB Output is correct
22 Correct 176 ms 17196 KB Output is correct
23 Correct 181 ms 18392 KB Output is correct
24 Correct 94 ms 17808 KB Output is correct
25 Correct 101 ms 17648 KB Output is correct
26 Correct 177 ms 17160 KB Output is correct
27 Correct 148 ms 22064 KB Output is correct
28 Correct 143 ms 21960 KB Output is correct
29 Correct 143 ms 22068 KB Output is correct
30 Correct 84 ms 21820 KB Output is correct
31 Correct 3 ms 4948 KB Output is correct
32 Incorrect 143 ms 21900 KB Output isn't correct
33 Halted 0 ms 0 KB -