제출 #709567

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
709567		aryan12	Stranded Far From Home (BOI22_island)	C++17	100 / 100	391 ms	55504 KiB

island

#include <bits/stdc++.h>
using namespace std;
#define int long long

mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());

const int N = 2e5 + 5;
vector<int> g[N];
int a[N];

struct node
{
    int index, sum, parent;
    bool merge;
    pair<int, int> children;

    node(int i, int s, int p, bool m)
    {
        index = i;
        sum = s;
        parent = p;
        merge = m;
        children = {-1, -1};
    }
} *reach[2 * N];

int Find(int idx)
{
    if(reach[idx]->parent == idx)
    {
        return idx;
    }
    return reach[idx]->parent = Find(reach[idx]->parent);
}

void Unite(int node1, int node2, int parent_node)
{
    reach[node1]->parent = parent_node;
    reach[node2]->parent = parent_node;
    reach[parent_node]->sum = reach[node1]->sum + reach[node2]->sum;
    reach[parent_node]->children = {node1, node2};
    reach[parent_node]->merge = false;
}

void dfs(int node, bool merge_parents)
{
    reach[node]->merge &= merge_parents;
    if(reach[node]->children.first == -1)
    {
        return;
    }
    dfs(reach[node]->children.first, reach[node]->merge);
    dfs(reach[node]->children.second, reach[node]->merge);
}

void Solve() 
{
    int n, m;
    cin >> n >> m;
    for(int i = n + 1; i <= 2 * n; i++)
    {
        reach[i] = new node(i, 0, i, false);
    }
    vector<array<int, 2> > order;
    for(int i = 1; i <= n; i++)
    {
        cin >> a[i];
        reach[i] = new node(i, a[i], i, false);
        order.push_back({a[i], i});
    }
    for(int i = 1; i <= m; i++)
    {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    sort(order.begin(), order.end());
    int new_index = n + 1;
    for(int i = 0; i < n; i++)
    {
        int current_index = order[i][1]; 
        for(int to: g[current_index])
        {
            if(a[to] <= a[current_index])
            {
                int parent_current_index = Find(current_index);
                int parent_index = Find(to);
                if(parent_index == parent_current_index)
                {
                    continue;
                }
                reach[parent_current_index]->merge = true;
                if(reach[parent_index]->sum >= a[current_index])
                {
                    reach[parent_index]->merge = true;
                }
                Unite(parent_current_index, parent_index, new_index);
                new_index = new_index + 1;
            }
        }
    }
    reach[new_index - 1]->merge = true;
    dfs(new_index - 1, true);
    for(int i = 1; i <= n; i++)
    {
        cout << ((reach[i]->merge) ? ('1') : ('0'));
    }
}

int32_t main() 
{
    auto begin = std::chrono::high_resolution_clock::now();
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t = 1;
    for(int i = 1; i <= t; i++) 
    {
        Solve();
    }
    auto end = std::chrono::high_resolution_clock::now();
    auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
    cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n"; 
    return 0;
}

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