Submission #961204

#	Time	Username	Problem	Language	Result	Execution time	Memory
961204		huutuan	Jail (JOI22_jail)	C++14	61 / 100	5044 ms	54004 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;
int n, m, up[LG][N], tin[N], tout[N], tdfs, dep[N], deg[N], vis[N];
pair<int, int> a[N];
int b[N], check;
vector<int> g[N], g2[N];

void dfs(int u, int p){
   tin[u]=++tdfs;
   up[0][u]=p;
   dep[u]=dep[p]+1;
   for (int k=1; k<LG; ++k) up[k][u]=up[k-1][up[k-1][u]];
   for (int v:g[u]) if (v!=p) dfs(v, u);
   tout[u]=tdfs;
}

bool is_ancestor(int u, int v){
   return tin[u]<=tin[v] && tin[v]<=tout[u];
}

int lca(int u, int v){
   if (dep[u]!=dep[v]){
      if (dep[u]<dep[v]) swap(u, v);
      int d=dep[u]-dep[v];
      for (int k=0; k<LG; ++k) if (d>>k&1) u=up[k][u];
   }
   if (u==v) return u;
   for (int k=LG-1; k>=0; --k) if (up[k][u]!=up[k][v]) u=up[k][u], v=up[k][v];
   return up[0][u];
}

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

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(1, 0);
   cin >> m;
   for (int i=1; i<=m; ++i){
      cin >> a[i].first >> a[i].second;
      b[i]=lca(a[i].first, a[i].second);
   }
   for (int i=1; i<=m; ++i) for (int j=1; j<=m; ++j) if (i!=j){
      if (is_ancestor(b[i], a[j].first) && (is_ancestor(a[j].first, a[i].first) || is_ancestor(a[j].first, a[i].second))) g2[j].push_back(i), ++deg[i];
      if (is_ancestor(b[i], a[j].second) && (is_ancestor(a[j].second, a[i].first) || is_ancestor(a[j].second, a[i].second))) g2[i].push_back(j), ++deg[j];
   }
   for (int i=1; i<=m; ++i) if (!deg[i]) dfs2(i);
   check&=accumulate(vis+1, vis+m+1, 0ll)==2*m;
   cout << (check?"Yes\n":"No\n");
   for (int i=1; i<=n; ++i) g[i].clear(), g2[i].clear(), deg[i]=vis[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: 0 / 5
• Subtask 2: 5 / 5
• Subtask 3: 16 / 16
• Subtask 4: 28 / 28
• Subtask 5: 12 / 12
• Subtask 6: 0 / 11
• Subtask 7: 0 / 23