QOJ.ac
QOJ
ID | 提交记录ID | 题目 | Hacker | Owner | 结果 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|
#542 | #334212 | #7222. The Great Hunt | ricky_lin | ricky_lin | Failed. | 2024-02-21 15:38:50 | 2024-02-21 15:38:51 |
详细
Extra Test:
Accepted
time: 695ms
memory: 16532kb
input:
9984 2 1 3 2 4 3 5 4 6 5 7 6 8 7 9 8 10 9 11 10 12 11 13 12 14 13 15 14 16 15 17 16 18 17 19 18 20 19 21 20 22 21 23 22 24 23 25 24 26 25 27 26 28 27 29 28 30 29 31 30 32 31 33 32 34 33 35 34 36 35 37 36 38 37 39 38 40 39 41 40 42 41 43 42 44 43 45 44 46 45 47 46 48 47 49 48 50 49 51 50 52 51 53 52 ...
output:
No
result:
ok
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#334212 | #7222. The Great Hunt | ricky_lin | AC ✓ | 264ms | 16808kb | C++14 | 2.2kb | 2024-02-21 14:40:25 | 2024-02-21 14:40:26 |
answer
#include<bits/stdc++.h>
using namespace std;
const int NN = 1e4 + 8;
int n;
inline int read(){
register char c = getchar();
register int res = 0;
while(!isdigit(c)) c = getchar();
while(isdigit(c)) res = res * 10 + c - '0',c = getchar();
return res;
}
struct Edge{
int to,next;
}edge[NN << 1];
int head[NN],cnt;
void init(){
memset(head,-1,sizeof(head));
cnt = 1;
}
void add_edge(int u,int v){
edge[++cnt] = {v,head[u]};
head[u] = cnt;
}
int fa[NN],dep[NN];
void dfs(int u,int father){
fa[u] = father;
dep[u] = dep[father] + 1;
for(int i = head[u]; i != -1; i = edge[i].next){
int v = edge[i].to;
if(v == father) continue;
dfs(v,u);
}
}
bitset<NN> e[NN];
int p[NN],rev[NN];
bitset<NN> vis;
//inline bool match(int u){
// bitset<NN> now = e[u] & vis;
// for(int v = now._Find_first(); v != NN; v = now._Find_next(v)){
// vis.reset(v);
// int x = p[v];
// if(x){
// if(match(x)){
// p[v] = u;
// return true;
// }
// }
// else{
// p[v] = u;
// return true;
// }
// }
// return false;
//} 递归版本 匈牙利
int q[NN],prex[NN],prey[NN];
inline bool match(int s){
int head,tail;
q[head = tail = 1] = s,vis.set();
int res = 0;
while(head <= tail){
int u = q[head++];
bitset<NN> now = e[u] & vis;
for(int v = now._Find_first(); v != NN; v = now._Find_next(v)){
vis.reset(v);
int x = p[v];
if(x) q[++tail] = x, prex[x] = u,prey[x] = v;
else p[v] = res = u;
if(res)break;
}
if(res)break;
}
if(!res) return false;
for(int i = res; i != s; i = prex[i]) p[prey[i]] = prex[i];
return true;
}//非递归版本 匈牙利
int main(){
n = read();
init();
for(int i = 1,u,v; i < n; ++i){
u = read();v = read();
add_edge(u,v);add_edge(v,u);
}
dfs(1,0);
for(int i = 1,u,v; i <= n; ++i){
u = read();v = read();
if(dep[u] < dep[v]) swap(u,v);
while(dep[u] > dep[v]) e[i].set(u),u = fa[u];
while(u != v) e[i].set(u),e[i].set(v),u = fa[u],v = fa[v];
e[i].set(u);
vis.set();
if(!match(i)){
puts("No");
return 0;
}
}
puts("Yes");
for(int i = 1; i <= n; ++i) rev[p[i]] = i;
for(int i = 1; i <= n; ++i) printf("%d ",rev[i]);
}