QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#815707 | #9866. Extracting Weights | Nana7 | WA | 5ms | 12836kb | C++14 | 2.7kb | 2024-12-15 16:37:12 | 2024-12-15 16:37:14 |
Judging History
answer
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<bitset>
#include<vector>
#define I inline
using namespace std;
const int N = 260;
struct bool_Matrix{
int n,m,x[N*N],id[N*N];
bitset<N> a[N*N];
I void init() {
for(int i=1;i<=n;++i) a[i].reset(),x[i]=0;
for(int i=1;i<=250*250;++i) id[i]=i;
n=m=0;
}
I int Gauss() {
// cout<<"!!"<<r<<endl;;
// for(int i=1;i<=n;++i) cout<<a[i]<<' '<<x[i]<<endl;
int r=1;
for(int i=1;i<=m&&r<=n;++i,++r) {
int ps=r;
for(int j=r+1;j<=n;++j) {
if(a[j][i]) {
ps=j;
}
}
if(ps!=r) swap(x[ps],x[r]),swap(a[ps],a[r]),swap(id[ps],id[r]);
if(!a[r][i]) {
r--;
continue;
}
for(int j=r+1;j<=n;++j) {
if(a[j][i]) {
a[j]^=a[r];
x[j]^=x[r];
}
}
}
if(r<=m) {
return m-r+1;
}
bool can=1;
for(int i=r;i<=n;++i) {
if(x[i]) can=0;
}
if(!can) return -1;
for(int i=m;i>=1;--i) {
for(int j=i-1;j>=1;--j) {
if(a[j][i]) a[j]^=a[i],x[j]^=x[i];
}
}
return 0;
}
}BM;
vector<int> q[N];
int n,k,dep[N],f[N];
void dfs(int x,int fa) {
dep[x]=dep[fa]+1; f[x]=fa;
for(auto &t:q[x]) {
if(t==fa) continue;
dfs(t,x);
}
}
I vector<int> trans(int x,int y) {
vector<int> ret;
if(x==y) {
ret.push_back(x);
return ret;
}
ret.push_back(x);
ret.push_back(y);
while(1) {
if(dep[x]<dep[y]) swap(x,y);
x=f[x];
if(x==y) break;
ret.push_back(x);
}
return ret;
}
#define pii pair<int,int>
int used[N*N];
I void solve() {
cin>>n>>k; BM.init();
for(int i=1;i<n;++i) {
int x,y; cin>>x>>y;
q[x].push_back(y);
q[y].push_back(x);
}
dfs(1,0);
BM.init(); BM.m=n;
vector<pii> query,rq;
for(int i=1;i<=n;++i) {
for(int j=i;j<=n;++j) {
vector<int> v=trans(i,j);
if(v.size()==k+1) {
query.push_back({i,j});
BM.n++;
for(auto &t:v) {
BM.a[BM.n][t]=1;
}
}
}
}
BM.a[++BM.n][1]=1;
bool_Matrix ck=BM,mk=BM;
if(ck.Gauss()) {
cout<<"NO"<<endl;
cout.flush();
return ;
}
for(int i=1;i<=n;++i) {
used[ck.id[i]]=1;
}
int sz=0; BM.init(); BM.m=n;
for(int i=0;i<query.size();++i) {
if(used[i+1]) {
sz++;
rq.push_back(query[i]);
BM.a[sz]=mk.a[i+1];
BM.x[sz]=mk.x[i+1];
}
}
cout<<"YES"<<endl;
cout.flush();
cout<<"? "<<sz<<' ';
for(auto &t:rq) {
cout<<t.first<<' '<<t.second<<' ';
}
cout<<endl;
cout.flush();
vector<int> v(sz+1);
for(int i=1;i<=sz;++i) cin>>v[i],BM.x[i]=v[i];
BM.Gauss();
cout<<"! ";
for(int i=2;i<=n;++i) cout<<BM.x[i]<<' '; cout<<endl;
cout.flush();
}
/*
4 1
1 2
2 3
2 4
1 3 2
*/
int main()
{
solve();
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 5ms
memory: 12836kb
input:
4 1 1 2 2 3 2 4 1 3 2
output:
YES ? 3 1 2 2 3 2 4 ! 3 2 0
result:
wrong answer Wrong answer in node 2, expected "1", but found "3".