oj.uz

Submission #573250

# Submission time Handle Problem Language Result Execution time Memory
573250 2022-06-06T09:54:12 Z MohamedFaresNebili Stranded Far From Home (BOI22_island) C++14
10 / 100
 1000 ms 14640 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];
        vector<int> adj[200001];
        void subtask2() {
            string res(N, '0');
            for(int l = 1; l <= N; l++) {
                if(S[l] != S[1]) continue;
                res[l - 1] = '1';
            }
            cout << res << "\n";
        }
 
        int32_t main() {
            ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
            cin >> N >> M; int R = 0; string res(N, '0');
            for(int l = 1; l <= N; l++)
                cin >> S[l], R += S[l];
            for(int l = 0; l < M; l++) {
                int U, V; cin >> U >> V;
                adj[U].pb(V); adj[V].pb(U);
            }
            bool ok = 1;
            for(int l = 2; l <= N; l++) {
                for(auto U : adj[l]) 
                  ok &= (U < l); 
                ok &= (S[l] <= S[l - 1]);
            }
            if(ok) {
                subtask2();
                return 0;
            }
            for(int l = 1; l <= N; l++) {
                int curr = 0;
                priority_queue<ii, vector<ii>, greater<ii>> pq;
                pq.push({0, l}); vector<bool> vis(N + 1, 0);
                while(!pq.empty()) {
                    int A = pq.top().second, B = pq.top().first; pq.pop();
                    if(vis[A] || (S[A] > curr && A != l)) continue;
                    vis[A] = 1; curr += S[A];
                    for(auto E : adj[A]) {
                        if(vis[E]) continue;
                        pq.push({S[E], E});
                    }
                }
                if(curr == R) res[l - 1] = '1';
            }
            cout << res << "\n";
        }

Compilation message

island.cpp: In function 'int32_t main()':
island.cpp:56:46: warning: unused variable 'B' [-Wunused-variable]
   56 |                     int A = pq.top().second, B = pq.top().first; pq.pop();
      |                                              ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 3 ms 5020 KB Output is correct
4 Correct 211 ms 5108 KB Output is correct
5 Correct 140 ms 5076 KB Output is correct
6 Correct 266 ms 5108 KB Output is correct
7 Correct 211 ms 5076 KB Output is correct
8 Correct 193 ms 5096 KB Output is correct
9 Correct 244 ms 5120 KB Output is correct
10 Correct 64 ms 5076 KB Output is correct
11 Correct 63 ms 5092 KB Output is correct
12 Correct 61 ms 5132 KB Output is correct
13 Correct 109 ms 5084 KB Output is correct
14 Correct 101 ms 5100 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 4 ms 4904 KB Output is correct
3 Execution timed out 1090 ms 14640 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Execution timed out 1086 ms 12972 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Execution timed out 1083 ms 14160 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 3 ms 5020 KB Output is correct
4 Correct 211 ms 5108 KB Output is correct
5 Correct 140 ms 5076 KB Output is correct
6 Correct 266 ms 5108 KB Output is correct
7 Correct 211 ms 5076 KB Output is correct
8 Correct 193 ms 5096 KB Output is correct
9 Correct 244 ms 5120 KB Output is correct
10 Correct 64 ms 5076 KB Output is correct
11 Correct 63 ms 5092 KB Output is correct
12 Correct 61 ms 5132 KB Output is correct
13 Correct 109 ms 5084 KB Output is correct
14 Correct 101 ms 5100 KB Output is correct
15 Correct 3 ms 4948 KB Output is correct
16 Correct 4 ms 4904 KB Output is correct
17 Execution timed out 1090 ms 14640 KB Time limit exceeded
18 Halted 0 ms 0 KB -