제출 #1305643

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1305643		cpismayilmmdv985	Stranded Far From Home (BOI22_island)	C++20	0 / 100	74 ms	17448 KiB

island

/***
 *       ██╗   ██╗ ██████╗ ██╗██████╗ 
 *       ██║   ██║██╔═══██╗██║██╔══██╗
 *       ██║   ██║██║   ██║██║██║  ██║
 *       ╚██╗ ██╔╝██║   ██║██║██║  ██║
 *        ╚████╔╝ ╚██████╔╝██║██████╔╝
 *         ╚═══╝   ╚═════╝ ╚═╝╚═════╝ 
***/

#include <queue>
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp> 
#include <ext/pb_ds/assoc_container.hpp> 
#ifdef LOCAL
#include ".debug.hpp"
#else
#define debug(...) 42
#endif
using namespace __gnu_pbds; 
using namespace std;
using ordered_set = tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>;

// String hashing: `https://codeforces.com/contest/126/submission/302225775`

/*** Defines ***/
#define uint unsigned int 
#define ll long long
#define ld long double
#define ull unsigned long long
#define sz(x) int32_t(x.size())
#define len(x) int32_t(x.length())
#define all(x) x.begin(), x.end()
#define int ll 

/*** Constraints ***/
const int MXN = 2e5 + 5;
const int MOD = 1e9 + 7;
const int INF = 2e9;
const ll INFL = 1e18;
const int DX[] = {1, -1, 0, 0}, DY[] = {0, 0, 1, -1};
const ll emptiness = (1LL << 40) - 1;
const int base1 = 47, base2 = 53;

/*** Runtime measurement ***/
clock_t startTime;
double getCurrentTime() {
    return (double)(clock() - startTime) / CLOCKS_PER_SEC;
}

vector<int> adj[MXN];
int N, A[MXN];

int bfs(int root) {
    vector<bool> used(N + 1);
    int res = A[root];
    priority_queue<array<int, 2>, vector<array<int, 2>>, greater<array<int, 2>>> pq;
    pq.push({A[root], root});
    while (!pq.empty()) {
        int node = pq.top()[1]; pq.pop();
        if (used[node] || res < A[node]) continue;
        if (node != root)   res += A[node];
        used[node] = true;
        for (auto &child : adj[node])   pq.push({A[child], child});
    }
    for (int i = 1; i <= N; i++)    if (!used[i])   return 0;
    return 1;
}

/*** run_case function ***/
void run_case() {
    int M;   cin >> N >> M;
    vector<int> pref(N + 1);
    for (int i = 1; i <= N; i++)    cin >> A[i], pref[i] = pref[i - 1] + A[i];
    for (int i = 0, U, V; i < M; i++)   cin >> U >> V, adj[U].push_back(V), adj[V].push_back(U);
    string ans = "";
    vector<int> bad(N + 5);
    for (int i = 1; i <= N; i++) {
        if (pref[N] - pref[i] < A[i])   bad[i + 1]++;
        if (pref[i - 1] < A[i])         bad[1]++, bad[i]--;
    }
    for (int i = 1; i <= N; i++)    bad[i] += bad[i - 1];
    for (int i = 1; i <= N; i++)    ans += (bad[i] ? '0' : '1');
    cout << ans;
    return;
}

/*** main function ***/
signed main() {
#ifndef VOID_DEBUG
    ios_base::sync_with_stdio(false), cin.tie(nullptr);
    startTime = clock();
#endif
 
    int test_case = 1; // cin >> test_case;
    for (int num_case = 1; num_case <= test_case; num_case++) {
        // cout << "#: " << num_case;
        run_case();
    }

    // printing time elapsed
    cerr << "\n\nTime elapsed: " << getCurrentTime() << "s\n";
    return 0;
}

/*
Counter tests:
*/

• Subtask 1: 0 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 15
• Subtask 4: 0 / 30
• Subtask 5: 0 / 35