Submission #962466

#	Time	Username	Problem	Language	Result	Execution time	Memory
962466		huutuan	Jail (JOI22_jail)	C++14	77 / 100	5067 ms	227020 KiB

jail

#include<bits/stdc++.h>

using namespace std;

// #define int long long
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define isz(x) ((int)x.size())
#define sumof(x) accumulate(all(x), 0ll)

const int N=2e5+10, LG=18;
vector<int> gg[N*6];
int idx[2][N*6], pos[2][N];
int deg[N*6];

struct SegmentTree{
   int n, m;
   void init(int _n){
      n=_n;
      m=n*2;
   }
   void build(int k, int l, int r, int ps[N], int pt[N]){
      if (l==r){
         idx[0][k]=pt[l];
         idx[1][k]=ps[l]?ps[l]+n:0;
         if (pt[l]) pos[0][pt[l]]=l;
         if (ps[l]) pos[1][ps[l]]=l;
         return;
      }
      idx[0][k]=++m;
      idx[1][k]=++m;
      int mid=(l+r)>>1;
      build(k<<1, l, mid, ps, pt);
      build(k<<1|1, mid+1, r, ps, pt);
      if (idx[0][k<<1]) gg[idx[0][k]].push_back(idx[0][k<<1]), ++deg[idx[0][k<<1]];
      if (idx[0][k<<1|1]) gg[idx[0][k]].push_back(idx[0][k<<1|1]), ++deg[idx[0][k<<1|1]];
      if (idx[1][k<<1]) gg[idx[1][k<<1]].push_back(idx[1][k]), ++deg[idx[1][k]];
      if (idx[1][k<<1|1]) gg[idx[1][k<<1|1]].push_back(idx[1][k]), ++deg[idx[1][k]];
   }
   void update(int k, int l, int r, int L, int R, int i, bool type){
      if (r<L || R<l) return;
      if (L<=l && r<=R){
         if (!type){
            if (idx[0][k]) gg[i+n].push_back(idx[0][k]), ++deg[idx[0][k]];
         }else{
            if (idx[1][k]) gg[idx[1][k]].push_back(i), ++deg[i];
         }
         return;
      }
      int mid=(l+r)>>1;
      update(k<<1, l, mid, L, R, i, type);
      update(k<<1|1, mid+1, r, L, R, i, type);
   }
   void _update(int k, int l, int r, int L, int R, int i, bool type){
      if (L<=pos[type][i] && pos[type][i]<=R){
         update(k, l, r, L, pos[type][i]-1, i, type);
         update(k, l, r, pos[type][i]+1, R, i, type);
      }else update(k, l, r, L, R, i, type);
   }
} st;

int n, m, tin[N], tout[N], tdfs, dep[N], vis[N*6], par[N], head[N], sz[N];
pair<int, int> a[N];
int check;
vector<int> g[N];

void dfs_sz(int u, int p){
   if (p) g[u].erase(find(all(g[u]), p));
   dep[u]=dep[p]+1;
   par[u]=p;
   sz[u]=1;
   for (int &v:g[u]){
      dfs_sz(v, u);
      if (sz[v]>sz[g[u][0]]) swap(v, g[u][0]);
   }
}

void dfs_hld(int u, int h){
   tin[u]=++tdfs;
   head[u]=h;
   for (int v:g[u]) dfs_hld(v, v==g[u][0]?h:v);
   tout[u]=tdfs;
}

void update(int u, int v, int i){
   while (head[u]!=head[v]){
      if (dep[head[u]]<dep[head[v]]) swap(u, v);
      st._update(1, 1, n, tin[head[u]], tin[u], i, 0);
      st._update(1, 1, n, tin[head[u]], tin[u], i, 1);
      u=par[head[u]];
   }
   if (dep[u]>dep[v]) swap(u, v);
   st._update(1, 1, n, tin[u], tin[v], i, 0);
   st._update(1, 1, n, tin[u], tin[v], i, 1);
}

void dfs2(int u){
   vis[u]=1;
   for (int v:gg[u]){
      if (!vis[v]) dfs2(v);
      else if (vis[v]==1) check=0;
   }
   vis[u]=2;
}

int ps[N], pt[N];

void solve(){
   check=1;
   cin >> n;
   for (int i=1; i<n; ++i){
      int u, v; cin >> u >> v;
      g[u].push_back(v);
      g[v].push_back(u);
   }
   dfs_sz(1, 0);
   dfs_hld(1, 1);
   cin >> m;
   for (int i=1; i<=m; ++i){
      cin >> a[i].first >> a[i].second;
      ps[tin[a[i].first]]=i;
      pt[tin[a[i].second]]=i;
   }
   st.init(n);
   st.build(1, 1, n, ps, pt);
   for (int i=1; i<=m; ++i) gg[i].push_back(i+n), ++deg[i+n];
   // for (int i=1; i<=n*6; ++i) for (int j:gg[i]) cout << i << ' ' << j << endl;
   for (int i=1; i<=m; ++i) update(a[i].first, a[i].second, i);
   // for (int i=1; i<=n*6; ++i) for (int j:gg[i]) cout << i << ' ' << j << endl;
   for (int i=1; i<=n*6; ++i) if (!deg[i]) dfs2(i);
   check&=accumulate(vis+1, vis+n*6+1, 0ll)==2*n*6;
   cout << (check?"Yes\n":"No\n");
   for (int i=1; i<=n*6; ++i) g[i].clear(), gg[i].clear(), deg[i]=vis[i]=0, ps[i]=pt[i]=0;
   tdfs=0;
}

int32_t main(){
   ios_base::sync_with_stdio(false);
   cin.tie(nullptr);
   int ntests=1;
   cin >> ntests;
   for (int i=1; i<=ntests; ++i) solve();
   return 0;
}

• 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: 0 / 23