제출 #554777

#제출 시각아이디문제언어결과실행 시간메모리
554777600MihneaJail (JOI22_jail)C++17
49 / 100
3343 ms1048576 KiB
#include <bits/stdc++.h>

bool home = 1;

using namespace std;

///const int N = 1200 + 7; // change this!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
const int N = 120000 + 7; // change this!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
const int K = 20;
const int C = 3;
int n;
int m;
int vis[C * N];
int act[C * N];
vector<int> g[N];
vector<int> relations[C * N];
vector<int> relations_inv[C * N];
pair<int, int> paths[N];
int first[N];
int last[N];
int top;
int depth[N];
int par[N];
int lg[2 * N];
pair<int, int> rmq[K][N];

void dfs(int a, int p, int dep) {
  depth[a] = dep;
  {
    vector<int> kids;
    for (auto &b : g[a]) {
      if (b == p) continue;
      kids.push_back(b);
      par[b] = a;
    }
    g[a] = kids;
  }
  rmq[0][++top] = {dep, a};
  first[a] = last[a] = top;

  for (auto &b : g[a]) {
    dfs(b, a, dep + 1);
    rmq[0][++top] = {dep, a};
    last[a] = top;
  }
}

int get_lca(int a, int b) {
  assert(1 <= a && a <= n);
  assert(1 <= b && b <= n);
  if (first[a] > last[b]) swap(a, b);
  a = first[a];
  b = last[b];
  assert(a <= b);
  int k = lg[b - a + 1];
  return min(rmq[k][a], rmq[k][b - (1 << k) + 1]).second;
}

bool is_on_path(int a, int query, int b) {
  int c = get_lca(a, b);
  if (get_lca(c, query) == c) {
    return get_lca(a, query) == query || get_lca(b, query) == query;
  }
  return 0;
}

vector<int> ord, now;

void dfs(int a) {
  vis[a] = 1;
  for (auto &b : relations[a]) if (!vis[b]) dfs(b);
  ord.push_back(a);
}

void dfs2(int a) {
  now.push_back(a);
  vis[a] = 1;
  for (auto &b : relations_inv[a]) if (!vis[b]) dfs2(b);
}

void addEdge(int v1, int v2) {
  relations[v1].push_back(v2);
}

void add_to(int id, int a, int c) {
  while (a != c) {
    addEdge(id, a);
    a = par[a];
  }
  addEdge(id, a);
}

void add_from(int id, int a, int c) {
  while (a != c) {
    addEdge(n + a, id);
    a = par[a];
  }
  addEdge(n + a, id);
}

signed main() {
#ifdef ONLINE_JUDGE
  home = 0;
#endif
  home = 0;

  if (home) {
    freopen("I_am_iron_man", "r", stdin);
  }
  else {
    ios::sync_with_stdio(0); cin.tie(0);
  }


  int Tests;
  cin >> Tests;
  for (int tc = 1; tc <= Tests; tc++) {
    cin >> n;
    ord.clear();
    for (int i = 1; i <= n; i++) g[i].clear();
    for (int i = 1; i <= 3 * n; i++) relations[i].clear(), vis[i] = 0, relations_inv[i].clear();
    for (int i = 1; i < n; i++) {
      int a, b;
      cin >> a >> b;
      g[a].push_back(b);
      g[b].push_back(a);
    }
    cin >> m;
    for (int i = 1; i <= m; i++) {
      cin >> paths[i].first >> paths[i].second;
    }
    top = 0;
    dfs(1, -1, 0);
    for (int i = 2; i <= top; i++) {
      lg[i] = 1 + lg[i / 2];
    }
    for (int k = 1; (1 << k) <= top; k++) {
      for (int i = 1; i + (1 << k) - 1 <= top; i++) {
        rmq[k][i] = min(rmq[k - 1][i], rmq[k - 1][i + (1 << (k - 1))]);
      }
    }

    for (int i = 1; i <= m; i++) {
      int a = paths[i].first, b = paths[i].second;
      int c = get_lca(a, b);


      add_to(2 * n + i, a, c);
      add_to(2 * n + i, b, c);

      add_from(2 * n + i, a, c);
      add_from(2 * n + i, b, c);

    }
    for (int i = 1; i <= m; i++) {
      int x = paths[i].first, y = paths[i].second;
      addEdge(x, 2 * n + i);
      addEdge(2 * n + i, n + y);
    }

    int dim = 2 * n + m;

    int good = 1;

    for (int i = 1; i <= dim; i++) {
      for (auto &j : relations[i]) {
        relations_inv[j].push_back(i);
      }
    }

    for (int i = 1; i <= dim; i++) if (!vis[i]) dfs(i);
    for (int i = 1; i <= dim; i++) vis[i] = 0;
    reverse(ord.begin(), ord.end());
    assert((int) ord.size() == dim);
    for (auto &x : ord) if (!vis[x]) {
      now.clear(), dfs2(x);
      int cnt = 0;
      for (auto &v : now) {
        cnt += (v > 2 * n);
      }
      if (cnt >= 2) {
        good = 0;
      }
    }


    cout << ((good) ? ("Yes") : ("No")) << "\n";
  }

}

컴파일 시 표준 에러 (stderr) 메시지

jail.cpp: In function 'int main()':
jail.cpp:108:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  108 |     freopen("I_am_iron_man", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...