oj.uz

Submission #573311

# Submission time Handle Problem Language Result Execution time Memory
573311 2022-06-06T11:56:36 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;

        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[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);
                    }
                    curr = Pr[j - 1] - Pr[i];
                    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 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 3 ms 6484 KB Output is correct
4 Correct 196 ms 5120 KB Output is correct
5 Correct 145 ms 5124 KB Output is correct
6 Correct 281 ms 5128 KB Output is correct
7 Correct 200 ms 5128 KB Output is correct
8 Correct 176 ms 5116 KB Output is correct
9 Correct 249 ms 5140 KB Output is correct
10 Incorrect 39 ms 6784 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 4 ms 6484 KB Output is correct
3 Correct 216 ms 25368 KB Output is correct
4 Correct 152 ms 25152 KB Output is correct
5 Correct 249 ms 21244 KB Output is correct
6 Correct 254 ms 21708 KB Output is correct
7 Correct 221 ms 21708 KB Output is correct
8 Correct 250 ms 21744 KB Output is correct
9 Correct 178 ms 22784 KB Output is correct
10 Correct 156 ms 21992 KB Output is correct
11 Correct 153 ms 22152 KB Output is correct
12 Correct 175 ms 21524 KB Output is correct
13 Incorrect 194 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 3 ms 6484 KB Output is correct
2 Execution timed out 1084 ms 26960 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6484 KB Output is correct
2 Execution timed out 1085 ms 14380 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 3 ms 6484 KB Output is correct
4 Correct 196 ms 5120 KB Output is correct
5 Correct 145 ms 5124 KB Output is correct
6 Correct 281 ms 5128 KB Output is correct
7 Correct 200 ms 5128 KB Output is correct
8 Correct 176 ms 5116 KB Output is correct
9 Correct 249 ms 5140 KB Output is correct
10 Incorrect 39 ms 6784 KB Output isn't correct
11 Halted 0 ms 0 KB -