oj.uz

Submission #573308

# Submission time Handle Problem Language Result Execution time Memory
573308 2022-06-06T11:48:59 Z MohamedFaresNebili Stranded Far From Home (BOI22_island) C++14
0 / 100
 1000 ms 27244 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;
 
        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] = 1e18; map<int, ii> DP; int Pr[200005]{0};
            for(int l = 1; l <= N; l++)
                Pr[l] = Pr[l - 1] + S[l];
            for(int l = 1; l <= N; l++) {
                int i = l - 1, j = l + 1; 
                while(i >= 1 || j <= N) {
                    int curr = Pr[j - 1] - Pr[i];
                    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);
                    }
                    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:123:46: warning: unused variable 'B' [-Wunused-variable]
  123 |                     int A = pq.top().second, B = pq.top().first; pq.pop();
      |                                              ^

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4992 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 3 ms 6496 KB Output is correct
4 Correct 200 ms 5120 KB Output is correct
5 Correct 143 ms 5116 KB Output is correct
6 Correct 265 ms 5128 KB Output is correct
7 Correct 213 ms 5116 KB Output is correct
8 Correct 151 ms 5124 KB Output is correct
9 Correct 253 ms 5140 KB Output is correct
10 Incorrect 36 ms 6740 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 3 ms 6484 KB Output is correct
3 Correct 188 ms 25364 KB Output is correct
4 Correct 137 ms 25224 KB Output is correct
5 Correct 260 ms 21340 KB Output is correct
6 Correct 229 ms 21732 KB Output is correct
7 Correct 238 ms 21708 KB Output is correct
8 Correct 262 ms 21692 KB Output is correct
9 Correct 190 ms 22844 KB Output is correct
10 Correct 137 ms 21976 KB Output is correct
11 Correct 149 ms 22184 KB Output is correct
12 Correct 184 ms 21524 KB Output is correct
13 Incorrect 196 ms 27244 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6484 KB Output is correct
2 Execution timed out 1082 ms 26956 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 6484 KB Output is correct
2 Execution timed out 1081 ms 14432 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4992 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 3 ms 6496 KB Output is correct
4 Correct 200 ms 5120 KB Output is correct
5 Correct 143 ms 5116 KB Output is correct
6 Correct 265 ms 5128 KB Output is correct
7 Correct 213 ms 5116 KB Output is correct
8 Correct 151 ms 5124 KB Output is correct
9 Correct 253 ms 5140 KB Output is correct
10 Incorrect 36 ms 6740 KB Output isn't correct
11 Halted 0 ms 0 KB -