Submission #709554

#	Time	Username	Problem	Language	Result	Execution time	Memory
709554		aryan12	Stranded Far From Home (BOI22_island)	C++17	0 / 100	335 ms	54088 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};
}

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 = 1; i <= n; i++)
    {
        // cout << "i = " << i << endl;
        int current_index = order[i][1]; 
        // cout << "current_index = " << current_index << endl;
        for(int to: g[current_index])
        {
            if(a[to] <= a[current_index])
            {
                int parent_current_index = Find(current_index);
                reach[parent_current_index]->merge = true;
                int parent_index = Find(to);
                if(reach[parent_index]->sum >= a[current_index])
                {
                    reach[parent_index]->merge = true;
                }
                if(parent_index == parent_current_index)
                {
                    continue;
                }
                // cout << "merging " << parent_current_index << " and " << parent_index << " to " << new_index << ".\n";
                Unite(parent_current_index, parent_index, new_index);
                new_index = new_index + 1;
            }
        }
    }
    reach[new_index - 1]->merge = true;
    // for(int i = 1; i < new_index; i++)
    // {
    //     cout << "current index: " << i << "\n";
    //     cout << "sum: " << reach[i]->sum << ", parent: " << reach[i]->parent << ", merge: " << reach[i]->merge << "\n";
    // }
    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;
    // cin >> t;
    for(int i = 1; i <= t; i++) 
    {
        //cout << "Case #" << 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: 0 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 15
• Subtask 4: 0 / 30
• Subtask 5: 0 / 35