Submission #1083963

#	Time	Username	Problem	Language	Result	Execution time	Memory
1083963		serifefedartar	Stranded Far From Home (BOI22_island)	C++17	100 / 100	418 ms	87072 KiB

island

#include <bits/stdc++.h>
using namespace std;
 
#define fast ios::sync_with_stdio(0);cin.tie(0)
typedef long long ll;
#define f first
#define s second
#define LOGN 21
const ll MOD = 1e9 + 7;
const ll MAXN = 2e5 + 100;
 
#define int long long
int val[MAXN], par[MAXN], sz[MAXN], sum[MAXN];
vector<vector<int>> graph;
map<int,vector<int>> mp;
set<int> st[MAXN];

int find(int node) {
    if (node == par[node])
        return node;
    return par[node] = find(par[node]);
}

void unite(int a, int b) {
    a = find(a);
    b = find(b);
    if (a == b)
        return ;
    if (sz[b] > sz[a])
        swap(a, b);
    sz[a] += sz[b];
    par[b] = a;
    sum[a] += sum[b];

    if (st[b].size() > st[a].size())
        swap(st[b], st[a]);
    for (auto u : st[b])
        st[a].insert(u);
}

signed main() {
    fast;
    for (int i = 0; i < MAXN; i++) {
        par[i] = i, sz[i] = 1, sum[i] = 0;
        st[i].insert(i);
    }
    int N, M;
    cin >> N >> M;

    graph = vector<vector<int>>(N+1, vector<int>());
    for (int i = 1; i <= N; i++) {
        cin >> val[i];
        sum[i] = val[i];
        mp[val[i]].push_back(i);
    }
    for (int i = 0; i < M; i++) {
        int a, b;
        cin >> a >> b;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }

    for (auto step : mp) {
        int vl = step.f;
        vector<int> nodes = step.s;

        for (auto node : nodes) {
            for (auto u : graph[node]) {
                if (val[u] < val[node]) {
                    if (sum[find(u)] < val[node])
                        st[find(u)] = set<int>();
                }
            }
        }

        for (auto node : nodes) {
            for (auto u : graph[node]) {
                if (val[u] <= val[node])
                    unite(node, u);
            }
        }
    }

    for (int i = 1; i <= N; i++) {
        if (st[find(i)].count(i))
            cout << "1";
        else
            cout << "0";
    }
}

Compilation message (stderr)

island.cpp: In function 'int main()':
island.cpp:64:13: warning: unused variable 'vl' [-Wunused-variable]
   64 |         int vl = step.f;
      |             ^~

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