QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#811338#9866. Extracting Weightsucup-team1525#WA 1ms3888kbC++201.8kb2024-12-12 18:06:592024-12-12 18:07:00

Judging History

你现在查看的是最新测评结果

  • [2024-12-12 18:07:00]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3888kb
  • [2024-12-12 18:06:59]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
const int N=250;
int n,k;
vector<int> e[N+5];
bitset<N+5> base[N+5];
vector<pair<int,int>> q;
int dep[N+5],fa[N+5];
void dfs(int u,int tf){
    fa[u]=tf; dep[u]=dep[tf]+1;
    for(auto v:e[u])
        if(v!=tf)
            dfs(v,u);
}
bool insert(bitset<N+5> &x){
    for(int i=1;i<=n;i++)
        if(x.test(i)){
            if(!base[i].test(i)){
                base[i]=x; return 1;
            }
            x^=base[i];
        }
    return 0;
}
int a[N+5][N+5];
int main(){
    scanf("%d %d",&n,&k);
    for(int i=1,u,v;i<n;i++){
        scanf("%d %d",&u,&v);
        e[u].push_back(v);
        e[v].push_back(u);
    }
    int rk=1;
    base[1][1]=1;
    for(int i=1;i<=n;i++){
        dfs(i,0);
        for(int j=1;j<=n;j++)
            if(dep[j]==k+1){
                bitset<N+5> tmp; tmp.reset();
                for(int t=j;t;t=fa[t]) tmp[t]=1;
                if(insert(tmp)){
                    q.push_back({i,j});
                    rk++;
                }
            }
    }
    if(rk<n){
        puts("No");
        return 0;
    }
    printf("? %d",n-1);
    for(auto [u,v]:q)
        printf(" %d %d",u,v);
    puts("");
    fflush(stdout);
    for(int i=1;i<n;i++){
        auto [u,v]=q[i-1];
        dfs(u,0);
        while(v){
            a[i][v]=1; v=fa[v];
        }
        scanf("%d",&a[i][n+1]);
    }
    a[n][1]=1; a[n][n+1]=0;
    for(int i=1;i<=n;i++){
        int j;
        for(j=i;j<=n;j++)
            if(a[j][i]) break;
        assert(j<=n);
        if(i!=j) swap(a[i],a[j]);
        for(j=1;j<=n;j++)
            if(i!=j&&a[j][i])
                for(int k=i;k<=n+1;k++)
                    a[j][k]^=a[i][k];
    }
    printf("!");
    for(int i=2;i<=n;i++)
        printf(" %d",a[i][n+1]);
    puts("");
    return 0;
}

詳細信息

Test #1:

score: 0
Wrong Answer
time: 1ms
memory: 3888kb

input:

4 1
1 2
2 3
2 4

output:

? 3 1 2 2 3 2 4

result:

wrong answer Token parameter [name=ok] equals to "?", doesn't correspond to pattern "[yY][eE][sS]|[nN][oO]"