Submission #779088

#	Time	Username	Problem	Language	Result	Execution time	Memory
779088		raysh07	Stranded Far From Home (BOI22_island)	C++17	100 / 100	207 ms	42068 KiB

island

#include <algorithm>
#include <iostream>
#include <vector>
#include <queue>
 
using namespace std;
 
const int maxn = 200005;
 
int n, m;
 
long long people[maxn];
 
vector<int> g[maxn];
 
bool answer[maxn];
 
int parent[maxn];
 
vector<int> nodes_in_component[maxn];
long long sum_component[maxn];
 
int root(int x)
{
    if (x == parent[x])
    {
        return x;
    }
 
    return parent[x] = root(parent[x]);
}
 
void connect(int x, int y)
{
    x = root(x);
    y = root(y);
 
    if (nodes_in_component[x].size() < nodes_in_component[y].size())
    {
        swap(x, y);
    }
 
    sum_component[x] += sum_component[y];
 
    for (auto node : nodes_in_component[y])
    {
        nodes_in_component[x].push_back(node);
    }
 
    parent[y] = x;
}
 
bool is_connected(int x, int y)
{
    return root(x) == root(y);
}
 
pair<int, int> sorted_nodes[maxn];
 
void fastIO()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}
 
int main()
{
    fastIO();
 
    cin >> n >> m;
 
    for (int i = 1; i <= n; ++i)
    {
        cin >> people[i];
        answer[i] = true;
        sorted_nodes[i] = make_pair(people[i], i);
    }
 
    for (int i = 1; i <= n; ++i)
    {
        sum_component[i] = people[i];
        nodes_in_component[i].push_back(i);
        parent[i] = i;
    }
 
    for (int i = 1; i <= m; ++i)
    {
        int x, y;
        cin >> x >> y;
 
        g[x].push_back(y);
        g[y].push_back(x);
    }
 
    /*for (int i = 1; i <= n; ++i)
    {
        sort(g[i].begin(), g[i].end(), [&](int x, int y)
        {
            return people[x] <= people[y];
        });
    }*/
 
    sort(sorted_nodes + 1, sorted_nodes + n + 1);
 
    for (int i = 1; i <= n; ++i)
    {
        int node = sorted_nodes[i].second;
 
        for (auto next_node : g[node])
        {
            if (people[node] < people[next_node])
            {
                continue;
            }
 
            int big_node = root(next_node);
 
            if (sum_component[big_node] < people[node])
            {
                for (auto blanked_node : nodes_in_component[big_node])
                {
                    answer[blanked_node] = false;
                }
            }
 
            if (is_connected(node, big_node) == false)
            {
                connect(node, big_node);
            }
        }
    }
 
    for (int i = 1; i <= n; ++i)
    {
        cout << answer[i];
    }
 
    cout << endl;
 
    return 0;
}

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