Submission #1189631

#	Time	Username	Problem	Language	Result	Execution time	Memory
1189631		epicci23	Jail (JOI22_jail)	C++20	72 / 100	1987 ms	1114112 KiB

jail

#include "bits/stdc++.h"
#define int long long
#define all(v) v.begin() , v.end()
#define sz(a) (int)a.size()
using namespace std;

const int N = 1e5 + 2e4 + 5;

vector<int> v[N],g[N];
int depth[N],vis[N],S[N],T[N],par[N];
array<int,2> ar[N];
bool ok = 1;

void dfs(int c,int p){
  par[c] = p;
  for(int x : v[c]){
    if(x == p) continue;
    depth[x] = depth[c] + 1;
    dfs(x, c);
  }
}

void Find(int c){
  if(vis[c] == 2 || !ok) return;
  if(vis[c] == 1){
    ok = 0;
    return;
  }
  vis[c] = 1;
  for(int u : g[c]) if(u != c) Find(u); 
  vis[c] = 2;
}

void _(){
  int n; cin >> n;
  
  ok = 1;
  for(int i=0;i<=n;i++){
  	vis[i] = 0;
  	v[i].clear(),g[i].clear();
  	S[i] = T[i] = -1;
  }

  for(int i=1;i<n;i++){
  	int a,b;
  	cin >> a >> b;
  	v[a].push_back(b);
  	v[b].push_back(a);
  }

  dfs(1, 1);
  
  int m; cin >> m;
  
  for(int i=1;i<=m;i++){
  	cin >> ar[i][0] >> ar[i][1];
  	S[ar[i][0]] = i;
  	T[ar[i][1]] = i;
  }

  for(int i=1;i<=m;i++){
    int a = ar[i][0], b = ar[i][1];

    while(a != b){
      if(depth[a] < depth[b]) swap(a, b);
      if(T[a] != -1){
      	g[T[a]].push_back(i);
      	//cout << "ekle : " << T[a] << ' ' << i << '\n';
      }
      if(S[a] != -1){
      	g[i].push_back(S[a]);
      	//cout << "ekle : " << i << ' ' << S[a] << '\n';
      }
      a = par[a];
    }

    if(T[a] != -1){
      g[T[a]].push_back(i);
     // cout << "ekle : " << T[a] << ' ' << i << '\n';
    }
    if(S[a] != -1){
      g[i].push_back(S[a]);
      //cout << "ekle : " << i << ' ' << S[a] << '\n';
    }
  }
  
  for(int i=1;i<=m;i++){
    sort(all(g[i]));
    g[i].erase(unique(all(g[i])),g[i].end());

    //cout << "bakalimm : " << i << '\n';
    //for(int u : g[i]) cout << u << ' ';
    //cout << '\n';
  }

  for(int i=1;i<=m;i++) Find(i);
  
  
  if(ok) cout << "Yes\n";
  else cout << "No\n";
}

int32_t main(){
  cin.tie(0); ios::sync_with_stdio(0);
  int tc=1;cin >> tc;
  while(tc--) _();
  return 0;
}

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