oj.uz

Submission #573317

# Submission time Handle Problem Language Result Execution time Memory
573317 2022-06-06T11:59:58 Z MohamedFaresNebili Stranded Far From Home (BOI22_island) C++14
35 / 100
 1000 ms 27320 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<ll, ll>;
        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;

        const int oo = 1e18 + 7;

        int N, M, S[200001], tin[200001];
        int timer, out[200001], st[800001];
        bool reach[200001];
        vector<int> adj[200001];
        string res;

        void update(int v, int l, int r, int p, int val) {
            if(l == r) {
                st[v] = val;
                return;
            }
            int md = (l + r) / 2;
            if(p <= md)
                update(v * 2, l, md, p, val);
            else update(v * 2 + 1, md + 1, r, p, val);
            st[v] = st[v * 2] + st[v * 2 + 1];
        }
        int query(int v, int l, int r, int lo, int hi) {
            if(l > hi || r < lo) return 0;
            if(l >= lo && r <= hi) return st[v];
            return query(v * 2, l, (l + r) / 2, lo, hi)
            + query(v * 2 + 1, (l + r) / 2 + 1, r, lo, hi);
        }
        void dfs(int v, int p) {
            tin[v] = timer;
            update(1, 0, N - 1, timer++, S[v]);
            for(auto u : adj[v]) {
                if(u == p) continue;
                dfs(u, v);
            }
            out[v] = timer - 1;
        }
        void solve(int v, int p) {
            int calc = query(1, 0, N - 1, tin[v], out[v]);
            if(calc < S[p]) return;
            reach[v] = reach[p]; res[v - 1] = '1';
            for(auto u : adj[v]) {
                if(u == p) continue;
                solve(u, v);
            }
        }
        void subtask2() {
            dfs(1, 1); reach[1] = 1; solve(1, 1);
            cout << res << "\n";
        }
        void subtask3() {
            S[0] = S[N + 1] = oo; map<int, ii> DP;
            int Pr[200005]; Pr[0] = 0;
            for(int l = 1; l <= N; l++)
                Pr[l] = Pr[l - 1] + S[l], DP[l] = {l - 1, l + 1};
            for(int l = 1; l <= N; l++) {
                int i = l - 1, j = l + 1;
                while(i >= 1 || j <= N) {
                    int curr = Pr[min(j - 1, N + 1)] - Pr[max(i, 0ll)];
                    if(S[i] > curr && S[j] > curr) break;
                    if(S[i] <= curr) {
                        ii P = DP[i];
                        i = min(i - 1, P.ff);
                        j = max(j, P.ss);
                    }
                    curr = Pr[min(j - 1, N + 1)] - Pr[max(i, 0ll)];
                    if(S[j] <= curr) {
                        ii P = DP[j];
                        i = min(i, P.ff);
                        j = max(j + 1, P.ss);
                    }
                }
                DP[l] = {i, j};
                if(i < 1 && j > N) 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; res.assign(N, '0');
            for(int l = 1; l <= N; l++)
                cin >> S[l], R += S[l];
            bool can = 1;
            for(int l = 0; l < M; l++) {
                int U, V; cin >> U >> V;
                adj[U].pb(V); adj[V].pb(U);
                can &= (abs(U - V) == 1);
            }
            if(can) {
                subtask3();
                return 0;
            }
            bool ok = 1;
            for(int l = 2; l <= N; l++) {
              	int v = 0;
                for(auto U : adj[l])
                  v += (U < l);
                ok &= (v == 1); 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:127:46: warning: unused variable 'B' [-Wunused-variable]
  127 |                     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 4948 KB Output is correct
2 Correct 3 ms 5040 KB Output is correct
3 Correct 3 ms 6484 KB Output is correct
4 Correct 198 ms 5116 KB Output is correct
5 Correct 147 ms 5108 KB Output is correct
6 Correct 271 ms 5128 KB Output is correct
7 Correct 211 ms 5132 KB Output is correct
8 Correct 156 ms 5076 KB Output is correct
9 Correct 248 ms 5076 KB Output is correct
10 Correct 4 ms 6740 KB Output is correct
11 Correct 5 ms 6804 KB Output is correct
12 Correct 4 ms 5204 KB Output is correct
13 Correct 7 ms 6740 KB Output is correct
14 Correct 103 ms 5196 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 6484 KB Output is correct
3 Correct 192 ms 25364 KB Output is correct
4 Correct 149 ms 25168 KB Output is correct
5 Correct 278 ms 21268 KB Output is correct
6 Correct 235 ms 21616 KB Output is correct
7 Correct 230 ms 21708 KB Output is correct
8 Correct 314 ms 21708 KB Output is correct
9 Correct 199 ms 22772 KB Output is correct
10 Correct 138 ms 21948 KB Output is correct
11 Correct 152 ms 22152 KB Output is correct
12 Correct 244 ms 21560 KB Output is correct
13 Correct 219 ms 27264 KB Output is correct
14 Correct 193 ms 27320 KB Output is correct
15 Correct 222 ms 27260 KB Output is correct
16 Correct 188 ms 27044 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6484 KB Output is correct
2 Correct 216 ms 27160 KB Output is correct
3 Correct 215 ms 27268 KB Output is correct
4 Correct 193 ms 27304 KB Output is correct
5 Correct 185 ms 27300 KB Output is correct
6 Correct 223 ms 27280 KB Output is correct
7 Correct 212 ms 27316 KB Output is correct
8 Correct 203 ms 27292 KB Output is correct
9 Correct 200 ms 27044 KB Output is correct
10 Correct 200 ms 27312 KB Output is correct
11 Correct 237 ms 27260 KB Output is correct

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6484 KB Output is correct
2 Execution timed out 1093 ms 14356 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 4948 KB Output is correct
2 Correct 3 ms 5040 KB Output is correct
3 Correct 3 ms 6484 KB Output is correct
4 Correct 198 ms 5116 KB Output is correct
5 Correct 147 ms 5108 KB Output is correct
6 Correct 271 ms 5128 KB Output is correct
7 Correct 211 ms 5132 KB Output is correct
8 Correct 156 ms 5076 KB Output is correct
9 Correct 248 ms 5076 KB Output is correct
10 Correct 4 ms 6740 KB Output is correct
11 Correct 5 ms 6804 KB Output is correct
12 Correct 4 ms 5204 KB Output is correct
13 Correct 7 ms 6740 KB Output is correct
14 Correct 103 ms 5196 KB Output is correct
15 Correct 3 ms 4948 KB Output is correct
16 Correct 3 ms 6484 KB Output is correct
17 Correct 192 ms 25364 KB Output is correct
18 Correct 149 ms 25168 KB Output is correct
19 Correct 278 ms 21268 KB Output is correct
20 Correct 235 ms 21616 KB Output is correct
21 Correct 230 ms 21708 KB Output is correct
22 Correct 314 ms 21708 KB Output is correct
23 Correct 199 ms 22772 KB Output is correct
24 Correct 138 ms 21948 KB Output is correct
25 Correct 152 ms 22152 KB Output is correct
26 Correct 244 ms 21560 KB Output is correct
27 Correct 219 ms 27264 KB Output is correct
28 Correct 193 ms 27320 KB Output is correct
29 Correct 222 ms 27260 KB Output is correct
30 Correct 188 ms 27044 KB Output is correct
31 Correct 3 ms 6484 KB Output is correct
32 Correct 216 ms 27160 KB Output is correct
33 Correct 215 ms 27268 KB Output is correct
34 Correct 193 ms 27304 KB Output is correct
35 Correct 185 ms 27300 KB Output is correct
36 Correct 223 ms 27280 KB Output is correct
37 Correct 212 ms 27316 KB Output is correct
38 Correct 203 ms 27292 KB Output is correct
39 Correct 200 ms 27044 KB Output is correct
40 Correct 200 ms 27312 KB Output is correct
41 Correct 237 ms 27260 KB Output is correct
42 Correct 3 ms 6484 KB Output is correct
43 Execution timed out 1093 ms 14356 KB Time limit exceeded
44 Halted 0 ms 0 KB -