oj.uz

Submission #573316

# Submission time Handle Problem Language Result Execution time Memory
573316 2022-06-06T11:58:39 Z MohamedFaresNebili Stranded Far From Home (BOI22_island) C++14
0 / 100
 1000 ms 27268 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];
            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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 3 ms 5024 KB Output is correct
3 Correct 3 ms 6484 KB Output is correct
4 Correct 200 ms 5124 KB Output is correct
5 Correct 149 ms 5112 KB Output is correct
6 Correct 272 ms 5076 KB Output is correct
7 Correct 199 ms 5132 KB Output is correct
8 Correct 160 ms 5116 KB Output is correct
9 Correct 247 ms 5076 KB Output is correct
10 Incorrect 38 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 25332 KB Output is correct
4 Correct 148 ms 25156 KB Output is correct
5 Correct 223 ms 21232 KB Output is correct
6 Correct 228 ms 21644 KB Output is correct
7 Correct 242 ms 21788 KB Output is correct
8 Correct 246 ms 21752 KB Output is correct
9 Correct 174 ms 22820 KB Output is correct
10 Correct 144 ms 22068 KB Output is correct
11 Correct 156 ms 22248 KB Output is correct
12 Correct 178 ms 21556 KB Output is correct
13 Incorrect 176 ms 27268 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6484 KB Output is correct
2 Execution timed out 1089 ms 26944 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 1093 ms 14588 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 5024 KB Output is correct
3 Correct 3 ms 6484 KB Output is correct
4 Correct 200 ms 5124 KB Output is correct
5 Correct 149 ms 5112 KB Output is correct
6 Correct 272 ms 5076 KB Output is correct
7 Correct 199 ms 5132 KB Output is correct
8 Correct 160 ms 5116 KB Output is correct
9 Correct 247 ms 5076 KB Output is correct
10 Incorrect 38 ms 6740 KB Output isn't correct
11 Halted 0 ms 0 KB -