oj.uz

Submission #573372

# Submission time Handle Problem Language Result Execution time Memory
573372 2022-06-06T13:06:18 Z MohamedFaresNebili Stranded Far From Home (BOI22_island) C++14
0 / 100
 341 ms 57204 KB 
#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];
        vector<int> adj[200001]; set<int> A[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;
            if(A[u].size() < A[v].size()) swap(A[u], A[v]);
            for(auto E : A[v]) A[u].insert(E);
            par[v] = u;
        }
 
        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});
                A[l].insert(l); par[l] = l;
            }
            sort(E.begin(), E.end());
            for(int l = 0; l < M; l++) {
                int U, V; cin >> U >> V;
                if(S[U] < S[V]) swap(U, V);
                adj[U].pb(V);
            }
            for(auto u : E) {
                int U = u.ss; U = findSet(U); int curr = 0;
                for(auto v : adj[U]) {
                    int V = findSet(v);
                    if(S[V] < S[U]) A[V].clear();
                    curr += S[V]; unionSet(U, V);
                }
                S[U] += curr;
            }
            string res(N, '0'); int R = findSet(1);
            for(auto u : A[R]) res[u - 1] = '1';
            cout << res << "\n";
        }

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14420 KB Output is correct
2 Correct 9 ms 14332 KB Output is correct
3 Correct 9 ms 14420 KB Output is correct
4 Correct 10 ms 14636 KB Output is correct
5 Correct 10 ms 14676 KB Output is correct
6 Incorrect 8 ms 14588 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14420 KB Output is correct
2 Correct 7 ms 14320 KB Output is correct
3 Incorrect 171 ms 39096 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 14416 KB Output is correct
2 Correct 341 ms 57204 KB Output is correct
3 Incorrect 315 ms 57092 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 14420 KB Output is correct
2 Incorrect 294 ms 38624 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14420 KB Output is correct
2 Correct 9 ms 14332 KB Output is correct
3 Correct 9 ms 14420 KB Output is correct
4 Correct 10 ms 14636 KB Output is correct
5 Correct 10 ms 14676 KB Output is correct
6 Incorrect 8 ms 14588 KB Output isn't correct
7 Halted 0 ms 0 KB -