Submission #1244009

#	Time	Username	Problem	Language	Result	Execution time	Memory
1244009		repmann	Jail (JOI22_jail)	C++20	0 / 100	7 ms	5960 KiB

jail

#include <bits/stdc++.h>
using namespace std;
//const int BLOCK = 300;
int T, N, M, glob;
vector <int> VG[120006], DAG[120006];
bool D[120006];
int A[120006], B[120006], I[2][120006];
int ET[240006], L[120006], R[120006];
int IN[120006];
//struct PATH
//{
//  int L, R;
//  const bool operator < (const PATH &p) const
//  {
//    if((L / BLOCK) != (p.L / BLOCK)) return (L / BLOCK) < (p.L / BLOCK);
//    return R < p.R;
//  }
//}P[120006];
inline void DFS(int node, int parent = 0)
{
  for(int x : VG[node])
  {
    if(x == parent) continue;
    ET[++glob] = node;
    if(!L[node]) L[node] = glob;
    DFS(x, node);
  }
  ET[++glob] = node;
  if(!L[node]) L[node] = glob;
  R[node] = glob;
  return;
}
inline void Compute(int u, int v)
{
  if(L[u] < L[v])
  {
    for(int j = L[u]; j <= L[v]; j++) D[ET[j]] = 0;
    for(int j = L[u]; j <= L[v]; j++) D[ET[j]] ^= 1;
    for(int j = L[u]; j <= L[v]; j++)
    {
      if(!D[ET[j]] || (ET[j] == u)) continue;
      if(I[0][ET[j]]) DAG[I[0][u]].push_back(I[0][ET[j]]);
    }
    return;
  }
  for(int j = L[v]; j <= L[u]; j++) D[ET[j]] = 0;
  for(int j = L[v]; j <= L[u]; j++) D[ET[j]] ^= 1;
  for(int j = L[v]; j <= L[u]; j++)
  {
    if(!D[ET[j]] || (ET[j] == u)) continue;
    if(I[0][ET[j]]) DAG[I[0][u]].push_back(I[0][ET[j]]);
  }
  return;
}
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;
  for(int i = 1; i <= N; i++) I[0][i] = I[1][i] = 0;
  for(int i = 1; i <= N; i++) VG[i].clear();
  int u, v;
  for(int i = 2; i <= N; i++)
  {
    cin >> u >> v;
    VG[u].push_back(v);
    VG[v].push_back(u);
  }
  glob = 0;
  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++) D[i] = 0;
  for(int i = 1; i <= M; i++)
  {
    cin >> A[i] >> B[i];
    I[0][A[i]] = I[1][B[i]] = i;
  }
  for(int i = 1; i <= M; i++) Compute(A[i], B[i]);
  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