oj.uz

Submission #594510

# Submission time Handle Problem Language Result Execution time Memory
594510 2022-07-12T15:06:45 Z Sam_a17 Werewolf (IOI18_werewolf) C++14
0 / 100
 3135 ms 95012 KB 
#include <bits/stdc++.h>
using namespace std;

#define pb push_back
#define ld long double
#define ll long long

#define sz(x) (int((x).size()))
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define uniq(x) x.resize(unique(all(x)) - x.begin());
#define lb lower_bound
#define ub upper_bound

const int maxN = 2e5 + 10, LOG = 21;
vector<int> adj[maxN];
int sz[maxN], p[maxN], up[maxN][LOG], depth[maxN];
int mini[maxN][LOG], maxi[maxN][LOG];

int dfs_sz(int node, int parent) {
  sz[node] = 1, p[node] = parent;
  for(auto u: adj[node]) {
    if(u == parent) continue;
 
    up[u][0] = node;
    maxi[u][0] = node;
    mini[u][0] = node;

    for(int i = 1; i < LOG; i++) {
      up[u][i] = up[up[u][i - 1]][i - 1];
      maxi[u][i] = max(maxi[u][i], maxi[up[u][i - 1]][i - 1]);
      mini[u][i] = min(mini[u][i], mini[up[u][i - 1]][i - 1]);
    }
 
    depth[u] = depth[node] + 1;
    sz[node] += dfs_sz(u, node);
  }
  return sz[node];
}

int lca(int a, int b) {
  if(a == b) {
    return a;
  }
 
  if(depth[a] > depth[b]) {
    swap(a, b);
  }
  int delta = depth[b] - depth[a];
  for(int i = 0; i < LOG; i++) {
    if(delta & (1 << i)) {
      b = up[b][i];
    }
  }
 
  if(a == b) {
    return a;
  }
 
  for(int i = LOG - 1; i >= 0; i--) {
    if(up[a][i] != up[b][i]) {
      a = up[a][i], b = up[b][i];
    }
  }
  return up[a][0];
}

pair<pair<int, int>, int> go(int b, int delta) {
  int mn = b, mx = b;
  for(int i = 0; i < LOG; i++) {
    if(delta & (1 << i)) {
      mn = min(mn, mini[b][i]);
      mx = max(mx, maxi[b][i]);
      b = up[b][i];
    }
  }
 
  return {{mn, mx}, b};
}
 
vector<int> check_validity(int N, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, std::vector<int> R) {
  int m = sz(X);
  vector<int> answ;
  if(m != N - 1 && N <= 3000) {
    for(int i = 0; i < m; i++) {
      adj[X[i]].pb(Y[i]);
      adj[Y[i]].pb(X[i]);
    }

    int q = sz(S);
    for(int i = 0; i < q; i++) {
      int s = S[i], e = E[i];
      int l = L[i], r = R[i];

      // from a
      vector<bool> p1(N), p2(N);
      queue<int> q;
      q.push(s); p1[s] = true;

      while(!q.empty()) {
        auto u = q.front();
        q.pop();

        for(auto j: adj[u]) {
          if(j < l || p1[j]) continue;
          p1[j] = true;
          q.push(j);
        }
      }

      q.push(e); p2[e] = true;

      while(!q.empty()) {
        auto u = q.front();
        q.pop();

        for(auto j: adj[u]) {
          if(j > r || p2[j]) continue;
          p2[j] = true;
          q.push(j);
        }
      }

      bool flag = true;
      for(int j = 0; j < N; j++) {
        if(p1[j] && p2[j]) {
          answ.pb(1);
          flag = false;
          break;
        }
      }

      if(flag) {
        answ.pb(0);
      }
    }

    return answ;
  } else if(m == N - 1) {
    for(int i = 0; i < m; i++) {
      adj[X[i]].pb(Y[i]);
      adj[Y[i]].pb(X[i]);
    }

    dfs_sz(0, 0);

    int q = sz(S);
    for(int i = 0; i < q; i++) {
      int s = S[i], e = E[i];
      int l = L[i], r = R[i];

      // go from e
      int lc = lca(s, e);

      int answ1 = 0, answ2 = 0;
      
      int ln = depth[s] - depth[lc], mx = s, st = s;
      for(int i = LOG - 1; i >= 0; i--) {
        if(mini[st][i] >= l && ln >= (1 << i)) {
          mx = max(mx, maxi[st][i]);
          st = up[st][i], answ1 += (1 << i);
          ln -= (1 << i);
        }
      }

      if(answ1 == (depth[s] - depth[lc])) {
        int answ3 = 0, ina = 0, inb = depth[e];
        while(ina <= inb) {
          int mid = (ina + inb) / 2;
          int sk = go(e, depth[e] - mid).second;
          assert(depth[sk] == mid);

          if(go(sk, mid).first.first >= l) {
            answ3 = mid;
            ina = mid + 1;
          } else {
            inb = mid - 1;
          }
        }

        answ1 += answ3;
      } 

      ln = depth[e] - depth[lc], mx = e, st = e;
      for(int i = LOG - 1; i >= 0; i--) {
        if(maxi[st][i] <= r && ln >= (1 << i)) {
          mx = max(mx, maxi[st][i]);
          st = up[st][i], answ2 += (1 << i);
          ln -= (1 << i);
        }
      }

      if(answ2 == (depth[e] - depth[lc])) {
        int answ4 = 0, ina = 0, inb = depth[s] - depth[lc];
        while(ina <= inb) {
          int mid = (ina + inb) / 2;
          int sk = go(s, depth[s] - mid).second;
          assert(depth[sk] == mid);

          if(go(sk, mid).first.second <= r) {
            answ4 = mid;
            ina = mid + 1;
          } else {
            inb = mid - 1;
          }
        }

        answ2 += answ4;
      } 

      int ob = depth[e] + depth[s] - 2 * depth[lc];
      answ2 = ob - answ2;

      if(answ1 >= answ2) {
        answ.pb(1);
      } else {
        answ.pb(0);
      }
    }
  }
  
  return answ;
}

Subtask #1
0 / 7.0

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

Subtask #2
0 / 8.0

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

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Incorrect 3135 ms 95012 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

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