Submission #1244091

#	Time	Username	Problem	Language	Result	Execution time	Memory
1244091		repmann	Jail (JOI22_jail)	C++20	0 / 100	8 ms	6216 KiB

jail

#include <bits/stdc++.h>
using namespace std;
int T, N, M, glob;
vector <int> VG[120006], DAG[120006];
int A[120006], B[120006];
int ET[240006], L[120006], R[120006], DP[120006], UP[20][120006];
int IN[120006];
inline void DFS(int node, int parent = 0)
{
  UP[0][node] = parent;
  for(int i = 1; UP[i - 1][UP[i - 1][node]]; i++) UP[i][node] = UP[i - 1][UP[i - 1][node]];
  for(int x : VG[node])
  {
    if(x == parent) continue;
    ET[++glob] = node;
    if(!L[node]) L[node] = glob;
    DP[x] = DP[node] + 1;
    DFS(x, node);
  }
  ET[++glob] = node;
  if(!L[node]) L[node] = glob;
  R[node] = glob;
  return;
}
inline int LCA(int u, int v)
{
//  cout << "lca: " << u << ' ' << v << '\n';
  if(DP[u] > DP[v]) swap(u, v);
  for(int i = 18; i >= 0; i--) if(DP[UP[i][v]] > DP[u]) v = UP[i][v];
  if(DP[u] != DP[v]) v = UP[0][v];
  for(int i = 18; i >= 0; i--) if(UP[i][u] != UP[i][v]) {u = UP[i][u]; v = UP[i][v];}
//  if(u == v) cout << v << '\n';
//  else cout << UP[0][v] << '\n';
  if(u == v) return v;
  return UP[0][v];
}
inline bool Contains(int u, int v, int node)
{
  int lca = LCA(u, v);
  return ((L[lca] <= L[node]) && (R[node] <= R[lca]) && (L[node] <= L[u]) && (R[u] <= R[node])) || (L[lca] <= L[node]) && (R[node] <= R[lca]) && (L[node] <= L[v]) && (R[v] <= R[node]);
}
inline bool Topological()
{
  int node, counter = 0;
  queue <int> Q;
  for(int i = 1; i <= M; i++) IN[i] = 0;
  for(int i = 1; i <= M; i++) for(int x : DAG[i]) IN[x]++;
//  for(int i = 1; i <= M; i++) {cout << i << ":\n"; for(int x : DAG[i]) cout << x << '\n';}
  for(int i = 1; i <= M; i++) if(!IN[i]) Q.push(i);
  while(Q.size())
  {
    node = Q.front();
    counter++;
    for(int x : DAG[node])
    {
      IN[x]--;
      if(!IN[x]) Q.push(x);
    }
    Q.pop();
  }
  return counter == M;
}
inline void Solve()
{
  cin >> N;
  int u, v;
  for(int i = 1; i <= N; i++) VG[i].clear();
  for(int i = 2; i <= N; i++)
  {
    cin >> u >> v;
    VG[u].push_back(v);
    VG[v].push_back(u);
  }
  glob = 0;
  for(int i = 1; i <= N; i++) L[i] = R[i] = DP[i] = 0;
  for(int j = 0; j < 20; j++) {for(int i = 1; i <= N; i++) UP[j][i] = 0;}
  DP[1] = 1;
  DFS(1);
//  cout << "?\n";
//  for(int i = 1; i <= glob; i++) cout << ET[i] << " \n"[i == glob];
  cin >> M;
  for(int i = 1; i <= M; i++) DAG[i].clear();
  for(int i = 1; i <= M; i++) cin >> A[i] >> B[i];
  for(int i = 1; i <= M; i++)
  {
    for(int j = 1; j <= M; j++)
    {
      if(i == j) continue;
      bool a = Contains(A[i], B[i], A[j]);
      bool b = Contains(A[i], B[i], B[j]);
      if(a && b) {cout << "No\n"; return;}
      if(a) DAG[i].push_back(j);
    }
  }
  if(Topological()) {cout << "Yes\n"; return;}
  cout << "No\n";
  return;
}
int main()
{
  ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  cin >> T;
  while(T--) Solve();

  return 0;
}

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