QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#811201 | #9866. Extracting Weights | shnshn | WA | 0ms | 5856kb | C++14 | 2.4kb | 2024-12-12 16:27:06 | 2024-12-12 16:27:07 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
//#define endl '\n'
using ll = long long;
using pii = pair<int, int>;
const double PI = acos(-1);
const int N = 250 + 10;
const int mod = 1e9 + 7;
bool b[N][N];
vector<int>e[N],path;
bitset<252> bit[N*N],bit1[N*N];
int n,k;
int id=0;
vector<pii>c;
void dfs(int x,int fa,int num,int be){
if(num==k){
if(b[x][be]==0){
id++;
for(int y:path){
bit[id][y]=1;
bit1[id][y]=1;
}
b[x][be]=b[be][x]=1;
bit[id][be]=1;
bit1[id][be]=1;
c.push_back({be,x});
}
return ;
}
for(int y:e[x]){
if(fa==y)continue;
path.push_back(y);
dfs(y,x,num+1,be);
path.pop_back();
}
}
bool bb[N*N];
vector<int>a(N+1);
bool check(){
for(int i=1;i<=n;i++){
int p=-1;
// cout<<"i="<<i<<endl;
// for(int j=1;j<=id;j++){
// cout<<bit[j]<<endl;
// }
for(int j=1;j<=id;j++){
if(bb[j])continue;
if(bit[j][i]==1){
p=j;
bb[j]=1;
a[i]=j;
break;
}
}
if(p==-1){
return 0;
}
for(int j=1;j<=id;j++){
if(bb[j])continue;
if(bit[j][i]==1){
bit[j]^=bit[p];
}
}
}
}
int w[N*N];
void check1(){
memset(bb,0,sizeof bb);
for(int i=1;i<=n;i++){
int p=-1;
for(int j=1;j<=id;j++){
if(bb[j])continue;
if(bit1[j][i]==1){
p=j;
bb[j]=1;
break;
}
}
for(int j=1;j<=id;j++){
if(bb[j])continue;
if(bit1[j][i]==1){
bit1[j]^=bit1[p];
w[j]^=w[p];
}
}
}
vector<int>ans(n+1);
for(int i=n;i>1;i--){
for(int j=i+1;j<=n;j++){
if(bit1[a[i]][j]==1){
w[a[i]]^=ans[j];
}
}
ans[i]=w[a[i]];
}
cout<<"! ";
for(int i=2;i<=n;i++){
cout<<ans[i]<<" ";
}
cout<<endl;
}
void solve() {
cin>>n>>k;
for(int i=1;i<n;i++){
int x,y;
cin>>x>>y;
e[x].push_back(y);
e[y].push_back(x);
}
bit[++id][1]=1;
bit1[id][1]=1;
c.push_back({0,0});
c.push_back({1,1});
for(int i=1;i<=n;i++){
dfs(i,0,0,i);
}
bool f=check();
if(f==0){
cout<<"NO"<<endl;
} else {
cout<<"YES"<<endl;
cout<<"? "<<n-1<<" ";
for(int i=2;i<=n;i++){
auto [x,y]=c[a[i]];
cout<<x<<" "<<y<<" ";
}
cout<<endl;
for(int i=2;i<=n;i++){
cin>>w[a[i]];
}
check1();
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr), cout.tie(nullptr);
int T = 1;
//cin>>T;
while (T--) {
solve();
}
return 0;
}
详细
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 5856kb
input:
4 1 1 2 2 3 2 4
output:
NO
result:
wrong answer Expected "YES", but found "NO"