QOJ.ac
QOJ
| ID | 提交记录ID | 题目 | Hacker | Owner | 结果 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|
| #544 | #334212 | #7222. The Great Hunt | ricky_lin | ricky_lin | Failed. | 2024-02-21 17:05:46 | 2024-02-21 17:05:46 |
詳細信息
Extra Test:
Accepted
time: 61ms
memory: 16376kb
input:
9919 1 4096 1 4666 1 9689 4096 8910 1 9365 1 8353 8353 8842 1 9801 1 6526 1 45 1 9554 8910 9569 9365 1279 45 2407 1279 4810 9554 619 8842 9699 9801 9234 1 4551 4810 4258 9234 4559 6526 6351 6351 1884 2407 7777 9689 3627 3627 4038 4551 5742 4038 4794 4258 7955 4794 337 1884 618 7777 4146 5742 2913 1 ...
output:
Yes 9875 3 9905 9914 5 16 9912 9 24 27 19 20 7 23 22 31 33 35 10 29 28 9884 9906 49 46 12 9911 43 11 32 17 25 18 34 57 36 21 15 13 55 45 26 51 41 52 64 37 70 38 40 44 56 53 73 50 39 59 75 58 54 74 61 9918 42 63 60 71 68 76 62 65 69 72 48 66 81 9916 67 83 85 77 87 84 79 94 97 80 88 96 100 91 122 86 9...
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]);
}