QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#182368#7222. The Great HuntckisekiRE 0ms0kbC++233.5kb2023-09-17 20:04:192023-09-17 20:04:20

Judging History

你现在查看的是最新测评结果

  • [2023-09-17 20:04:20]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:0kb
  • [2023-09-17 20:04:19]
  • 提交

answer

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;

#ifdef local
#define safe std::cerr<<__PRETTY_FUNCTION__<<" line "<<__LINE__<<" safe\n"
#define debug(args...) qqbx(#args, args)
#define orange(args...) danb(#args, args)
using std::cerr;
template <typename ...T> void qqbx(const char *s, T ...args) {
  int cnt = sizeof...(T);
  ((cerr << "\e[1;32m(" << s << ") = ("), ..., (cerr << args << (--cnt ? ", " : ")\e[0m\n")));
}
template <typename I> void danb(const char *s, I L, I R) {
  cerr << "\e[1;32m[ " << s << " ] = [ ";
  for (int f = 0; L != R; ++L) cerr << (f++ ? ", " : "") << *L;
  cerr << " ]\e[0m\n";
}
#else
#define safe ((void)0)
#define debug(...) ((void)0)
#define orange(...) ((void)0)
#endif // local
#define all(v) begin(v),end(v)

namespace {
const int maxn = 10005;
struct BipartiteMatching {
  int n;
  vector<bitset<maxn>> g, dg, t;
  vector<int> mx, my;
  vector<int> dis;
  bitset<maxn> visx, visy;

  BipartiteMatching(int n_) : n(n_), g(n), dg(n), mx(n, -1), my(n, -1) {}
  void add_edge(int x, int y) {
    g[x].set(y);
  }

  bool bfs() {
    dis.assign(n, -1);
    for (int i = 0; i < n; i++) dg[i].reset();

    vector<int> q;
    for (int i = 0; i < n; i++)
      if (mx[i] == -1) {
        q.push_back(i);
        dis[i] = 0;
      }

    bool found = false;
    bitset<maxn> nvis;
    nvis.set();

    while (!q.empty()) {
      vector<int> nq;
      for (int i: q) {
        t[i] = g[i] & nvis;
      }
      for (int i: q) {
        for (size_t j = t[i]._Find_first(); j < maxn; j = t[i]._Find_next(j)) {
          nvis.reset(j);
          dg[i].set(j);
          if (my[j] == -1) {
            found = true;
          } else if (dis[my[j]] == -1) {
            nq.push_back(my[j]);
            dis[my[j]] = dis[i] + 1;
          }
        }
      }
      q = nq;
    }
    return found;
  }

  bool dfs(int i) {
    if (visx[i]) return false;
    visx[i] = true;
    dg[i] &= ~visy;
    for (size_t j = dg[i]._Find_first(); j < maxn; j = dg[i]._Find_next(j)) {
      visy[j] = true;
      if (my[j] == -1 || dfs(my[j])) {
        my[j] = i;
        mx[i] = j;
        return true;
      }
    }
    return false;
  }

  int solve() {
    int ans = 0;
    while (bfs()) {
      visx.reset();
      visy.reset();
      for (int i = 0; i < n; i++)
        if (mx[i] == -1 && dfs(i))
          ++ans;
    }
    return ans;
  }
};
}

signed main() {
  ios_base::sync_with_stdio(0), cin.tie(0);
  int N;
  cin >> N;

  vector<int> pa(N), dep(N), tin(N), ord;

  {
    vector<vector<int>> g(N);
    for (int i = 1; i < N; i++) {
      int x, y;
      cin >> x >> y;
      --x, --y;
      g[x].emplace_back(y);
      g[y].emplace_back(x);
    }
    const auto dfs = [&](auto self, int i, int f) -> void {
      tin[i] = ord.size(); ord.push_back(i);
      pa[i] = f;
      for (int j: g[i]) {
        if (j == f) continue;
        dep[j] = dep[i] + 1;
        self(self, j, i);
      }
    };

    dfs(dfs, 0, -1);
  }

  BipartiteMatching b(N);
  for (int i = 0; i < N; i++) {
    int x, y;
    cin >> x >> y;
    --x, --y;
    debug(x, y);
    while (x != y) {
      if (dep[x] > dep[y]) swap(x, y);
      b.add_edge(tin[y], i);
      y = pa[y];
    }
    b.add_edge(tin[x], i);
  }

  if (b.solve() == N) {
    cout << "Yes\n";
    for (int i = 0; i < N; i++)
      cout << ord[b.my[i]] + 1 << (i+1==N ? '\n' : ' ');
  } else {
    cout << "No\n";
  }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Runtime Error

input:

10
2 1
3 1
6 1
8 2
4 3
9 6
5 4
7 8
10 7
8 7
10 2
7 2
10 1
3 1
5 2
5 1
6 1
9 2
3 4

output:


result: