Submission #735079

#	Time	Username	Problem	Language	Result	Execution time	Memory
735079		cadmiumsky	Jail (JOI22_jail)	C++17	100 / 100	1553 ms	338600 KiB

jail

#include <bits/stdc++.h>
#define all(x) (x).begin(),(x).end()
using namespace std;

using ll = long long;
using ld = long double;

const int nmax = 5e5 + 5;
//#define int ll
#define sz(x) ((int)(x).size())

using pii = pair<int,int>;
using tii = tuple<int,int,int>;

pii chains[nmax];

namespace Tree {
  
  int pin[nmax], pout[nmax], area[nmax], inp;
  int p[nmax], jump[nmax], d[nmax];
  int pch[nmax];
  
  namespace G {
      vector<vector<int>> g;
      vector<int> occ;
      
      // Low level
      int newnode() { 
        g.emplace_back();
        occ.emplace_back(0);
        return sz(g) - 1;
      }
      void addedge(int x, int y) {
        if(x != 0 && y != 0)
          g[x].emplace_back(y);
      }
      bool dfs(int node) {
        if(occ[node] == 2) return 0;
        if(occ[node] == 1) return 1;
        occ[node] = 1;
        bool ok = 0;
        for(auto x : g[node])
          ok |= dfs(x);
        occ[node] = 2;
        return ok;
      }
      bool findcyc() {
        bool found = 0;
        for(int i = 0; !found && i < sz(g); i++) {
          found |= dfs(i);
        }
        return found;
      }
      // High Level
      
      int inspre[17][nmax]; // sus in jos
      int dinspre[17][nmax]; // jos in sus
      int lg2[nmax];
      
      void init(vector<int> T, vector<int> A) {
        int n = sz(T);
        for(int i = 2; i < n; i++)
          lg2[i] = lg2[i >> 1] + 1;
        for(int i = 0; i < n; i++) 
          inspre[0][i] = T[i];
        for(int step = 1; step < 17; step++) {
          for(int i = 0; i + (1 << step) <= n; i++) {
            inspre[step][i] = newnode();
            addedge(inspre[step][i], inspre[step - 1][i]);
            addedge(inspre[step][i], inspre[step - 1][i + (1 << step - 1)]);
          }
        }
        n = sz(A);
        for(int i = 0; i < n; i++) 
          dinspre[0][i] = A[i];
        for(int step = 1; step < 17; step++) {
          for(int i = 0; i + (1 << step) <= n; i++) {
            dinspre[step][i] = newnode();
            addedge(dinspre[step - 1][i], dinspre[step][i]);
            addedge(dinspre[step - 1][i + (1 << step - 1)], dinspre[step][i]);
          }
        }
        return;
      }
      void pushdown(int X, int l, int r) {
        int step = lg2[r - l + 1];
        addedge(X, inspre[step][l]);
        addedge(X, inspre[step][r - (1 << step) + 1]);
        //cerr << X << " --> " << l << ", " << r << '\n';
      }
      void pushup(int X, int l, int r) {
        int step = lg2[r - l + 1];
        addedge(dinspre[step][r - (1 << step) + 1], X);
        addedge(dinspre[step][l], X);
        //cerr << X << " <-- " << l << ", " << r << '\n';
      }
      void push(int X, int l, int r, int pass = 0) {
        if(r < l) return;
        int mid = -1;
        if(pass == 0) mid = pin[chains[X].first];
        else if(pass == 1) mid = pin[chains[X].second];
        
        if(l <= mid && mid <= r) {
          push(X, l, mid - 1, pass + 1),
          push(X, mid + 1, r, pass + 1);
          return;
        }
        if(pass != 2) {
          push(X, l, r, pass + 1);
          return;
        }
        pushup(X, l, r);
        pushdown(X, l, r);
        return;
      }
      
      void init(int n) {
        g.clear();
        occ.clear();
        g.resize(n + 1);
        occ.resize(n + 1, 0);
      }
    }
  
  vector<int> g[nmax];
  
  void initstd(int node, int f) {
    p[node] = f;
    jump[node] = f;
    d[node] = d[f] + 1;
    if(d[jump[f]] - d[jump[jump[f]]] == d[f] - d[jump[f]])
      jump[node] = jump[jump[f]];
      
    //cerr << node << '>' << jump[node] << '\n';
      
    area[node] = 1;
    for(auto x : g[node]) {
      if(x == f) continue;
      initstd(x, node);
      area[node] += area[x];
    }
    return;
  }
  
  bool isanc(int x, int y) { return pin[x] <= pin[y] && pout[y] <= pout[x]; }
  int lca(int x, int y) {
    while(!isanc(x, y)) {
      if(!isanc(jump[x], y)) x = jump[x];
      x = p[x];
    }
    return x;
  }
  
  namespace HLD {
    
    void initp(int node, int f) {
      pin[node] = inp++;
      //cerr << node << ' ' << inp - 1 << '\n';
      int atrs = -1;
      for(auto x : g[node]) {
        if(x == f) continue;
        if(atrs == -1 || area[atrs] < area[x]) atrs = x;
      }
      if(atrs == -1) { pout[node] = inp - 1; return; }
      pch[atrs] = pch[node];
      initp(atrs, node);
      for(auto x : g[node]) {
        if(x == f || x == atrs) continue;
        pch[x] = x;
        initp(x, node);
      }
      
      pout[node] = inp - 1;
      return;
    }
    void pushQ(int x, int y, int X) {
      if(isanc(x, y) && x != y) return;
      //cerr << X << '\t' << x << ' ' << y << '\n';
      if(pch[x] == pch[y]) { G::push(X, pin[y], pin[x]); return; }
      G::push(X, pin[pch[x]], pin[x]);
      pushQ(p[pch[x]], y, X);
    }
  }
  

  
  void init(int n) {
    inp = 0;
    for(int i = 0; i <= n; i++)
      g[i].clear();
  }
}

void driver() {
  int n, m;
  cin >> n;
  Tree::init(n);
  for(int i = 1, x, y; i < n; i++) {
    cin >> x >> y;
    Tree::g[x].emplace_back(y);
    Tree::g[y].emplace_back(x);
  }
  Tree::g[0].emplace_back(1);
  Tree::g[1].emplace_back(0);
  Tree::initstd(0, 0);
  Tree::HLD::initp(0, 0);
  cin >> m;
  vector<int> ends(n + 1), starts(n + 1);
  for(int i = 1, S, T; i <= m; i++) {
    cin >> S >> T;
    starts[Tree::pin[S]] = i;
    ends[Tree::pin[T]] = i;
    chains[i] = pii{S, T};
  }
  //for(auto x : ends) cerr << x << ' '; cerr << '\n';
  //for(auto x : starts) cerr << x << ' '; cerr << '\n';
  
  Tree::G::init(m);
  Tree::G::init(ends, starts);
  for(int i = 1, S, T; i <= m; i++) {
    tie(S, T) = chains[i];
    int L = Tree::lca(S, T);
    Tree::HLD::pushQ(S, L, i);
    Tree::HLD::pushQ(T, L, i);
    Tree::G::pushdown(i, Tree::pin[S], Tree::pin[S]);
    Tree::G::pushup(i, Tree::pin[T], Tree::pin[T]);
  }
  cout << (Tree::G::findcyc()? "No\n" : "Yes\n");
}

signed main() {
  int T;
  cin >> T;
  while(T--) driver();
  
}

/**
      Anul asta se da centroid.
-- Surse oficiale
*/

Compilation message (stderr)

jail.cpp: In function 'void Tree::G::init(std::vector<int>, std::vector<int>)':
jail.cpp:70:70: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   70 |             addedge(inspre[step][i], inspre[step - 1][i + (1 << step - 1)]);
      |                                                                 ~~~~~^~~
jail.cpp:80:54: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   80 |             addedge(dinspre[step - 1][i + (1 << step - 1)], dinspre[step][i]);
      |                                                 ~~~~~^~~

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 16 / 16
• Subtask 4: 28 / 28
• Subtask 5: 12 / 12
• Subtask 6: 11 / 11
• Subtask 7: 23 / 23