oj.uz

Submission #573306

# Submission time Handle Problem Language Result Execution time Memory
573306 2022-06-06T11:47:55 Z MohamedFaresNebili Stranded Far From Home (BOI22_island) C++14
0 / 100
 1000 ms 27212 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; DP[l] = {l, l};
                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 2 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 3 ms 6484 KB Output is correct
4 Correct 193 ms 5108 KB Output is correct
5 Correct 151 ms 5108 KB Output is correct
6 Correct 264 ms 5076 KB Output is correct
7 Correct 198 ms 5132 KB Output is correct
8 Correct 163 ms 5208 KB Output is correct
9 Correct 249 ms 5140 KB Output is correct
10 Incorrect 30 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 4 ms 6484 KB Output is correct
3 Correct 189 ms 25404 KB Output is correct
4 Correct 149 ms 25144 KB Output is correct
5 Correct 216 ms 21256 KB Output is correct
6 Correct 228 ms 21648 KB Output is correct
7 Correct 229 ms 21668 KB Output is correct
8 Correct 245 ms 21744 KB Output is correct
9 Correct 175 ms 22788 KB Output is correct
10 Correct 140 ms 22000 KB Output is correct
11 Correct 145 ms 22224 KB Output is correct
12 Correct 175 ms 21524 KB Output is correct
13 Incorrect 198 ms 27212 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 6552 KB Output is correct
2 Execution timed out 1085 ms 26908 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 1091 ms 14396 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 2 ms 4948 KB Output is correct
3 Correct 3 ms 6484 KB Output is correct
4 Correct 193 ms 5108 KB Output is correct
5 Correct 151 ms 5108 KB Output is correct
6 Correct 264 ms 5076 KB Output is correct
7 Correct 198 ms 5132 KB Output is correct
8 Correct 163 ms 5208 KB Output is correct
9 Correct 249 ms 5140 KB Output is correct
10 Incorrect 30 ms 6740 KB Output isn't correct
11 Halted 0 ms 0 KB -