oj.uz

Submission #598002

# Submission time Handle Problem Language Result Execution time Memory
598002 2022-07-17T09:16:10 Z slime Stranded Far From Home (BOI22_island) C++14
10 / 100
 1000 ms 25904 KB 
#include "bits/stdc++.h"
using namespace std;
#define int long long
const int MAXN = 3e5 + 10;
const int MOD = 1e9 + 7;
#define ll __int128
mt19937_64 rng((int)std::chrono::steady_clock::now().time_since_epoch().count());
int rnd(int x, int y) {
  int u = uniform_int_distribution<int>(x, y)(rng); return u;
}
ll read() { int x; cin >> x; return (ll)x; }
long long bm(long long b, long long p) {
  if(p==0) return 1 % MOD;
  long long r = bm(b, p >> 1);
  if(p&1) return (((r*r) % MOD) * b) % MOD;
  return (r*r) % MOD;
}
long long inv(long long b) { 
  return bm(b, MOD-2);
}
long long f[MAXN];
long long nCr(int n, int r) { 
  long long ans = f[n]; ans *= inv(f[r]); ans %= MOD;
  ans *= inv(f[n-r]); ans %= MOD; return ans;
}
long long fib[MAXN], lucas[MAXN];
void precomp() { 
  for(int i=0; i<MAXN; i++) f[i] = (i == 0 ? 1 % MOD : (f[i-1] * i) % MOD); 
  lucas[0] = 2;
  lucas[1] = 1;
  for(int i=2; i<MAXN; i++) lucas[i] = (lucas[i-2] + lucas[i-1]) % MOD;
  fib[0] = 0;
  fib[1] = 1;
  for(int i=2; i<MAXN; i++) fib[i] = (fib[i-2] + fib[i-1]) % MOD;
}
int fastlog(int x) {
  return (x == 0 ? -1 : 64 - __builtin_clzll(x) - 1);
}
void gay(int i) { cout << "Case #" << i << ": "; }
int csb(int l, int r, int k) { // count number of [l, r] such that i & 2^k > 0
  if(l > r) return 0;
  if(l == 0) {
    int s = r / (1ll << (k+1)); // number of complete cycles
    int t = r % (1ll << (k+1));
    int ans = s * (1ll << k);
    ans += (t >= (1ll << k) ? t - (1ll << k) + 1 : 0);
    return ans;
  }
  else return csb(0, r, k) - csb(0, l - 1, k);
}
int lis(vector<int> a) {
  int n = a.size();
  int bucket[n+1];
  for(int i=1; i<=n; i++) bucket[i] = 1e18;
  int ans = 1;
  for(int x: a) {
    auto it = lower_bound(bucket + 1, bucket +n +1, x);
    int d = distance(bucket, it);
    ans = max(ans, d);
    bucket[d] = min(bucket[d], x);
  }
  return ans;
}
struct disjoint_sets {
  vector<int> dsu;
  vector<int> sizes;
  public:
  void resize(int n) {
    dsu.resize(n + 10);
    sizes.resize(n + 10);
    for(int i=0; i<n+10; i++) dsu[i] = i;
  }
  void set_size(int i, int x) {
    sizes[i] = x;
  }
  int get_size(int i) {
    return sizes[set_of(i)];
  }
  int set_of(int u) {
    if(dsu[u] == u) return u;
    return dsu[u] = set_of(dsu[u]);
  }
  void union_sets(int u, int v) {
    int o = sizes[set_of(u)] + sizes[set_of(v)];
    dsu[set_of(u)] = set_of(v);
    sizes[set_of(u)] = o;
  }
};

void solve(int tc) {
  int n, m;
  cin >> n >> m;
  disjoint_sets dsu;
  dsu.resize(n);
  pair<int, int> s[n+1];
  for(int i=1; i<=n; i++) {
    cin >> s[i].first;
    s[i].second = i;
    dsu.set_size(i, s[i].first);

  }
  vector<int >adj[n+1];
  for(int i=1; i<=m; i++) {
    int a, b; cin >> a >> b;
    adj[a].push_back(b);
    adj[b].push_back(a);
  }
  sort(s+1, s+n+1);
  bool done[n+1], bad[n+1];
  for(int i=1; i<=n; i++) done[i] = 0, bad[i] = 0;
  for(int i=1; i<=n; i++) {
    int node = s[i].second, val = s[i].first;
   // cout << val << " " << node << " o\n";
    for(int x: adj[node]) {
      if(dsu.set_of(node) != dsu.set_of(x) && done[x]) {
        if(dsu.get_size(x) < val) {
          for(int j=1; j<=n; j++) {
            if(dsu.set_of(j) == dsu.set_of(x)) {
              bad[j] = 1;
           //   cout << j << " bad\n";
            }
          }
        }
        dsu.union_sets(node, x);
    //    cout << "union " << node << " " << x << "\n";
      }
    }
    done[node] = 1;
  }
  for(int i=1; i<=n; i++) cout << (bad[i] ? 0 : 1);
  cout << "\n";
}

/*
Set is bad if:
Sum(Set) < Min(Outgoing S)

If set bad, answer = 0 for all in set
Use KRT to update

4 3
5 7 3 5
1 2
2 3
3 4
*/
int32_t main() {
  precomp();
  ios::sync_with_stdio(0); cin.tie(0);
  int t = 1; //cin >> t;
  for(int i=1; i<=t; i++) solve(i);
}
// I don't know geometry.
// Teaming is unfair.

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 7328 KB Output is correct
2 Correct 7 ms 7252 KB Output is correct
3 Correct 7 ms 7252 KB Output is correct
4 Correct 13 ms 7508 KB Output is correct
5 Correct 16 ms 7508 KB Output is correct
6 Correct 10 ms 7432 KB Output is correct
7 Correct 12 ms 7424 KB Output is correct
8 Correct 11 ms 7400 KB Output is correct
9 Correct 8 ms 7508 KB Output is correct
10 Correct 18 ms 7512 KB Output is correct
11 Correct 19 ms 7536 KB Output is correct
12 Correct 18 ms 7588 KB Output is correct
13 Correct 8 ms 7512 KB Output is correct
14 Correct 14 ms 7512 KB Output is correct

Subtask #2
0 / 10.0

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

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7252 KB Output is correct
2 Execution timed out 1086 ms 24872 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 7252 KB Output is correct
2 Execution timed out 1098 ms 25892 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 7328 KB Output is correct
2 Correct 7 ms 7252 KB Output is correct
3 Correct 7 ms 7252 KB Output is correct
4 Correct 13 ms 7508 KB Output is correct
5 Correct 16 ms 7508 KB Output is correct
6 Correct 10 ms 7432 KB Output is correct
7 Correct 12 ms 7424 KB Output is correct
8 Correct 11 ms 7400 KB Output is correct
9 Correct 8 ms 7508 KB Output is correct
10 Correct 18 ms 7512 KB Output is correct
11 Correct 19 ms 7536 KB Output is correct
12 Correct 18 ms 7588 KB Output is correct
13 Correct 8 ms 7512 KB Output is correct
14 Correct 14 ms 7512 KB Output is correct
15 Correct 7 ms 7252 KB Output is correct
16 Correct 7 ms 7252 KB Output is correct
17 Execution timed out 1085 ms 25904 KB Time limit exceeded
18 Halted 0 ms 0 KB -