QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#804729#9866. Extracting Weightsucup-team1134#RE 1ms3752kbC++234.0kb2024-12-08 03:01:262024-12-08 03:01:27

Judging History

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

  • [2024-12-08 03:01:27]
  • 评测
  • 测评结果:RE
  • 用时:1ms
  • 内存:3752kb
  • [2024-12-08 03:01:26]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return true; } return false; }
#define vi vector<int>
#define vl vector<ll>
#define vii vector<pair<int,int>>
#define vll vector<pair<ll,ll>>
#define vvi vector<vector<int>>
#define vvl vector<vector<ll>>
#define vvii vector<vector<pair<int,int>>>
#define vvll vector<vector<pair<ll,ll>>>
#define vst vector<string>
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define mkunique(x) sort(all(x));(x).erase(unique(all(x)),(x).end())
#define fi first
#define se second
#define mp make_pair
#define si(x) int(x.size())
const int mod=998244353,MAX=300005,INF=15<<26;

vi G[MAX];
int de[MAX],par[MAX];
vi AA;

void DFS(int u,int p){
    if(u) AA.pb(u);
    par[u]=p;
    for(int to:G[u]){
        if(to==p) continue;
        de[to]=de[u]+1;
        DFS(to,u);
    }
}

void solve(int u,int p,vii &ask){
    if(de[u]>=2) ask.pb(mp(par[par[u]],u));
    for(int to:G[u]){
        if(to==p) continue;
        solve(to,u,ask);
    }
}

typedef vector<int> vec;
typedef vector<vec> mat;

vec gauss_jordan(const mat& A,const vec &b){
    int n=A.size();
    mat B(n,vec(n+1));
    
    for(int i=0;i<n;i++) for(int j=0;j<n;j++) B[i][j]=A[i][j];
    
    for(int i=0;i<n;i++) B[i][n]=b[i];
    
    int rank=0;
    
    for(int j=0;j<n;j++){
        int pivot=-1;
        
        for(int i=rank;i<n;i++){
            if(B[i][j]){
                pivot=i;
                break;
            }
        }
        
        if(pivot==-1) continue;
        
        swap(B[pivot],B[rank]);
        
        for(int i=0;i<n;i++){
            if(i!=rank){
                if(B[i][j]){
                    for(int k=0;k<=n;k++) B[i][k]^=B[rank][k];
                }
            }
        }
        
        rank++;
    }
    
    bool ok=true;
    
    for(int i=rank;i<n;i++){
        if(B[i][n]) ok=false;
    }
    
    if(!ok) return vec();
    
    vec x(n);
    
    for(int i=0;i<rank;i++) x[i]=B[i][n];
    return x;
}

using B=bitset<255>;

vector<B> basis;

bool add(B x){
    for(B tmp:basis){
        int z=tmp._Find_first();
        if(z<250){
            if(x[z]){
                x^=tmp;
            }
        }
    }
    if(x.count()){
        basis.push_back(x);
        return 1;
    }
    return 0;
}

int main(){
    
    int N,K;cin>>N>>K;
    for(int i=0;i<N-1;i++){
        int a,b;cin>>a>>b;a--;b--;
        G[a].pb(b);
        G[b].pb(a);
    }
    DFS(0,-1);
    
    vii ask;
    for(int a=0;a<N;a++){
        for(int b=a+1;b<N;b++){
            B de={};
            int x=a,y=b;
            int d=0;
            while(x!=y){
                d++;
                if(de[x]>de[y]) swap(x,y);
                if(y) de[y-1]=true;
                y=par[y];
            }
            if(d!=K) continue;
            if(x) de[x-1]=true;
            
            if(add(de)){
                ask.pb(mp(a,b));
            }
        }
    }
    
    if(si(basis)==N-1){
        cout<<"Yes"<<endl;
        cout<<"? "<<si(ask);
        for(auto [a,b]:ask) cout<<" "<<a+1<<" "<<b+1;
        cout<<endl;
        vi res;
        for(int i=0;i<si(ask);i++){
            int x;cin>>x;
            res.pb(x);
        }
        mat A(si(ask),vi(N-1));
        for(int i=0;i<si(ask);i++){
            int a=ask[i].fi,b=ask[i].se;
            int x=a,y=b;
            while(x!=y){
                if(de[x]>de[y]) swap(x,y);
                if(y) A[i][y-1]=true;
                y=par[y];
            }
            if(x) A[i][x-1]=true;
        }
        cout<<"!";
        auto ress=gauss_jordan(A,res);
        for(int i=0;i<N-1;i++) cout<<" "<<ress[i];
        cout<<endl;
    }else{
        cout<<"No"<<endl;
    }
}



Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3752kb

input:

4 1
1 2
2 3
2 4
1 3 2

output:

Yes
? 3 1 2 2 3 2 4
! 1 2 3

result:

ok OK 3 numbers

Test #2:

score: 0
Accepted
time: 1ms
memory: 3492kb

input:

5 2
1 2
2 3
3 4
3 5
1 2 3 4

output:

Yes
? 4 1 3 2 4 2 5 4 5
! 4 5 3 2

result:

ok OK 4 numbers

Test #3:

score: 0
Accepted
time: 1ms
memory: 3548kb

input:

6 2
1 2
2 3
3 4
4 5
4 6

output:

No

result:

ok Correct

Test #4:

score: -100
Runtime Error

input:

250 1
108 84
37 129
33 68
131 135
26 173
186 25
35 104
78 123
52 115
239 44
166 149
127 210
185 212
246 64
249 143
137 101
82 209
244 29
15 242
20 62
243 151
81 10
42 159
65 71
71 105
166 192
214 225
97 87
86 208
43 60
235 54
77 107
28 147
195 2
45 153
104 180
63 250
205 165
220 206
24 92
12 41
233 ...

output:


result: