Submission #573386

#	Time	Username	Problem	Language	Result	Execution time	Memory
573386		MohamedFaresNebili	Stranded Far From Home (BOI22_island)	C++14	100 / 100	306 ms	48380 KiB

island

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

        using namespace std;
        using namespace __gnu_pbds;

        using ll = long long;
        using ii = pair<int, int>;
        using vi = vector<int>;

        #define pb push_back
        #define pp pop_back
        #define ff first
        #define ss second
        #define lb lower_bound
        #define int ll

        typedef tree<int, null_type, less<int>, rb_tree_tag,
            tree_order_statistics_node_update> indexed_set;

        int N, M, S[200001], par[200001], anc[200001];
        vector<int> adj[200001], sub[200001], D[200001];
        int res[200001]; bool vis[200001], processed[200001];

        int findSet(int v) {
            if(par[v] == v) return v;
            return par[v] = findSet(par[v]);
        }
        void unionSet(int u, int v) {
            u = findSet(u), v = findSet(v);
            if(u == v) return;
            par[v] = u; S[u] += S[v];
        }
        void dfs(int v, bool state) {
            res[v] &= state;
            for(auto u : D[v]) {
                dfs(u, res[v]);
            }
        }

        int32_t main() {
            ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
            cin >> N >> M; vector<ii> E;
            for(int l = 1; l <= N; l++) {
                cin >> S[l]; E.pb({S[l], l});
                par[l] = l; sub[l].pb(l); res[l] = 1;
            }
            sort(E.begin(), E.end());
            for(int l = 0; l < M; l++) {
                int U, V; cin >> U >> V;
                adj[U].pb(V), adj[V].pb(U);
            }
            for(auto e : E) {
                int U = e.ss;
                for(auto v : adj[U]) {
                    if(!processed[v]) continue;
                    int V = findSet(v);
                    if(S[V] < S[U]) res[anc[V]] = 0;
                    V = anc[V];
                    if(!vis[V]) {
                        vis[V] = 1; D[U].pb(V);
                    }
                }
                for(auto v : adj[U]) {
                    if(!processed[v]) continue;
                    int V = findSet(v);
                    V = anc[V]; vis[V] = 0;
                }
                for(auto V : adj[U]) {
                    if(!processed[V]) continue;
                    unionSet(U, V);
                }
                int V = findSet(U); anc[V] = U;
                processed[U] = 1;
            }
            dfs(E[N - 1].ss, 1);
            for(int l = 1; l <= N; l++)
                cout << res[l];
        }

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