QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#182368 | #7222. The Great Hunt | ckiseki | RE | 0ms | 0kb | C++23 | 3.5kb | 2023-09-17 20:04:19 | 2023-09-17 20:04:20 |
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