oj.uz

Submission #573245

# Submission time Handle Problem Language Result Execution time Memory
573245 2022-06-06T09:52:06 Z MohamedFaresNebili Stranded Far From Home (BOI22_island) C++14
10 / 100
 1000 ms 14596 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 = (adj[1].size() == N - 1);
            for(int l = 2; l <= N; l++) {
                ok &= (adj[l].size() == 1);
                int U = adj[l][0];
                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:41:38: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
   41 |             bool ok = (adj[1].size() == N - 1);
      |                        ~~~~~~~~~~~~~~^~~~~~~~
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 2 ms 4932 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 200 ms 5096 KB Output is correct
5 Correct 147 ms 5096 KB Output is correct
6 Correct 262 ms 5108 KB Output is correct
7 Correct 196 ms 5100 KB Output is correct
8 Correct 153 ms 5096 KB Output is correct
9 Correct 242 ms 5124 KB Output is correct
10 Correct 62 ms 5084 KB Output is correct
11 Correct 62 ms 5076 KB Output is correct
12 Correct 66 ms 5116 KB Output is correct
13 Correct 113 ms 5088 KB Output is correct
14 Correct 87 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 2 ms 4948 KB Output is correct
3 Execution timed out 1086 ms 14596 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 1085 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 1084 ms 14264 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4932 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 200 ms 5096 KB Output is correct
5 Correct 147 ms 5096 KB Output is correct
6 Correct 262 ms 5108 KB Output is correct
7 Correct 196 ms 5100 KB Output is correct
8 Correct 153 ms 5096 KB Output is correct
9 Correct 242 ms 5124 KB Output is correct
10 Correct 62 ms 5084 KB Output is correct
11 Correct 62 ms 5076 KB Output is correct
12 Correct 66 ms 5116 KB Output is correct
13 Correct 113 ms 5088 KB Output is correct
14 Correct 87 ms 5100 KB Output is correct
15 Correct 3 ms 4948 KB Output is correct
16 Correct 2 ms 4948 KB Output is correct
17 Execution timed out 1086 ms 14596 KB Time limit exceeded
18 Halted 0 ms 0 KB -