oj.uz

Submission #1092969

# Submission time Handle Problem Language Result Execution time Memory
1092969 2024-09-25T14:26:55 Z duckindog Stranded Far From Home (BOI22_island) C++17
20 / 100
 200 ms 31056 KB 
#include <bits/stdc++.h>

using namespace std;

const int N = 200'000 + 10;
int n, m;
int s[N];
vector<int> ad[N];

namespace sub1 { 
  static const int SZ = 2000 + 10;
  bool f[SZ];
  void solve() { 
    for (int i = 1; i <= n; ++i) { 
      using pii = pair<int, int>;
      priority_queue<pii, vector<pii>, greater<>> q;
      for (const auto& v : ad[i]) q.push({s[v], v});
      
      memset(f, false, sizeof f);
      long long total = s[i]; f[i] = true;
      while (q.size()) { 
        auto [cnt, u] = q.top(); q.pop();
        if (f[u] || total < cnt) continue;
        total += cnt;
        f[u] = true;
        for (const auto& v : ad[u]) 
          if (!f[v]) q.push({s[v], v});
      }

      cout << *min_element(f + 1, f + n + 1);
    }
    cout << "\n";
  }
}

namespace sub2 { 
  long long d[N];  
  void dfs0(int u, int p = -1) { 
    d[u] = s[u];
    for (const auto& v : ad[u]) { 
      if (v == p) continue;
      dfs0(v, u);
      d[u] += d[v];
    }
  }

  bool f[N];
  void dfs1(int u, int p = -1) { 
    for (const auto& v : ad[u]) {
      if (v == p) continue; 
      if (d[v] >= s[u]) f[v] |= f[u];
      dfs1(v, u);
    }
  }
  
  void solve() { 
    dfs0(1);
    dfs1(f[1] = 1);

    for (int i = 1; i <= n; ++i) cout << f[i];
    cout << "\n";
  }
}

int32_t main() { 
  cin.tie(0)->sync_with_stdio(0);

  cin >> n >> m;
  for (int i = 1; i <= n; ++i) cin >> s[i];
  for (int i = 1; i <= m; ++i) { 
    int u, v; cin >> u >> v;
    ad[u].push_back(v);
    ad[v].push_back(u);
  }

  if (n <= 2000 && m <= 2000) { sub1::solve(); return 0; }

  bool sub2 = (m == n - 1);
  for (int i = 1; i < n; ++i) sub2 &= (s[i] >= s[i + 1]);
  if  (sub2) { sub2::solve(); return 0; }
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4956 KB Output is correct
2 Correct 2 ms 4988 KB Output is correct
3 Correct 2 ms 4956 KB Output is correct
4 Correct 162 ms 5256 KB Output is correct
5 Correct 111 ms 5212 KB Output is correct
6 Correct 200 ms 5248 KB Output is correct
7 Correct 170 ms 5212 KB Output is correct
8 Correct 130 ms 5212 KB Output is correct
9 Correct 176 ms 5212 KB Output is correct
10 Correct 55 ms 5260 KB Output is correct
11 Correct 47 ms 5208 KB Output is correct
12 Correct 43 ms 5260 KB Output is correct
13 Correct 92 ms 5212 KB Output is correct
14 Correct 68 ms 5464 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5076 KB Output is correct
2 Correct 3 ms 5168 KB Output is correct
3 Correct 102 ms 23484 KB Output is correct
4 Correct 87 ms 22104 KB Output is correct
5 Correct 91 ms 18000 KB Output is correct
6 Correct 93 ms 18520 KB Output is correct
7 Correct 88 ms 18524 KB Output is correct
8 Correct 85 ms 18640 KB Output is correct
9 Correct 73 ms 18320 KB Output is correct
10 Correct 61 ms 18108 KB Output is correct
11 Correct 58 ms 18300 KB Output is correct
12 Correct 76 ms 17244 KB Output is correct
13 Correct 79 ms 29488 KB Output is correct
14 Correct 79 ms 29600 KB Output is correct
15 Correct 86 ms 31056 KB Output is correct
16 Correct 65 ms 30032 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4952 KB Output is correct
2 Incorrect 59 ms 16492 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4952 KB Output is correct
2 Incorrect 71 ms 16596 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4956 KB Output is correct
2 Correct 2 ms 4988 KB Output is correct
3 Correct 2 ms 4956 KB Output is correct
4 Correct 162 ms 5256 KB Output is correct
5 Correct 111 ms 5212 KB Output is correct
6 Correct 200 ms 5248 KB Output is correct
7 Correct 170 ms 5212 KB Output is correct
8 Correct 130 ms 5212 KB Output is correct
9 Correct 176 ms 5212 KB Output is correct
10 Correct 55 ms 5260 KB Output is correct
11 Correct 47 ms 5208 KB Output is correct
12 Correct 43 ms 5260 KB Output is correct
13 Correct 92 ms 5212 KB Output is correct
14 Correct 68 ms 5464 KB Output is correct
15 Correct 2 ms 5076 KB Output is correct
16 Correct 3 ms 5168 KB Output is correct
17 Correct 102 ms 23484 KB Output is correct
18 Correct 87 ms 22104 KB Output is correct
19 Correct 91 ms 18000 KB Output is correct
20 Correct 93 ms 18520 KB Output is correct
21 Correct 88 ms 18524 KB Output is correct
22 Correct 85 ms 18640 KB Output is correct
23 Correct 73 ms 18320 KB Output is correct
24 Correct 61 ms 18108 KB Output is correct
25 Correct 58 ms 18300 KB Output is correct
26 Correct 76 ms 17244 KB Output is correct
27 Correct 79 ms 29488 KB Output is correct
28 Correct 79 ms 29600 KB Output is correct
29 Correct 86 ms 31056 KB Output is correct
30 Correct 65 ms 30032 KB Output is correct
31 Correct 2 ms 4952 KB Output is correct
32 Incorrect 59 ms 16492 KB Output isn't correct
33 Halted 0 ms 0 KB -