QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#804704#9866. Extracting Weightsucup-team1134#WA 8ms3908kbC++235.5kb2024-12-08 02:37:452024-12-08 02:37:46

Judging History

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

  • [2024-12-08 02:37:46]
  • 评测
  • 测评结果：WA
  • 用时：8ms
  • 内存：3908kb
查看
  • [2024-12-08 02:37:45]
  • 提交

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){
        for(int i=0;i<250;i++){
            if(x[i]){
                if(tmp[i]){
                    x=x^tmp;
                    break;
                }
            }else{
                if(tmp[i]){
                    break;
                }
            }
        }
    }
    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);
    
    if(K==1){
        cout<<"YES"<<endl;
        vii ask;
        for(int i:AA){
            ask.pb(mp(par[i],i));
        }
        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);
        }
        vi ans(N);
        for(int i=0;i<si(ask);i++){
            ans[ask[i].se]=ans[ask[i].fi]^res[i];
        }
        cout<<"!";
        for(int i=1;i<N;i++){
            cout<<" "<<ans[i];
        }
        cout<<endl;
    }else if(K>=3){
        cout<<"NO"<<endl;
    }else{
        vii ask;
        for(int i=0;i<N;i++){
            vi X;
            for(int to:G[i]){
                if(to==par[i]) continue;
                X.pb(to);
            }
            for(int j=1;j<si(X);j++){
                B de={};
                int x=X[0],y=X[j],z=par[x];
                
                if(x) de[x-1]=1;
                if(y) de[y-1]=1;
                if(z) de[z-1]=1;
                
                if(add(de)){
                    ask.pb(mp(x,y));
                }
            }
            if(de[i]>=2){
                B de={};
                int x=par[par[i]],y=par[i],z=i;
                
                if(x) de[x-1]=1;
                if(y) de[y-1]=1;
                if(z) de[z-1]=1;
                
                if(add(de)){
                    ask.pb(mp(x,z));
                }
            }
        }
        
        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;
                if(de[b]>=2&&par[par[b]]==a){
                    int x=a,y=par[b],z=b;
                    if(x) A[i][x-1]=1;
                    if(y) A[i][y-1]=1;
                    if(z) A[i][z-1]=1;
                }else{
                    int x=a,y=b,z=par[a];
                    assert(par[b]==z);
                    if(x) A[i][x-1]=1;
                    if(y) A[i][y-1]=1;
                    if(z) A[i][z-1]=1;
                }
            }
            cout<<"!";
            auto ress=gauss_jordan(A,res);
            for(int i=0;i<N-1;i++) cout<<" "<<ress[i];
            cout<<endl;
        }else{
            cout<<"NO"<<endl;
        }
    }
}
源文件, 语言: C++23

详细

Test #1:

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

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: 3568kb

input:

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

output:

YES
? 4 4 5 1 3 2 4 2 5
! 4 5 3 2

result:

ok OK 4 numbers

Test #3:

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

input:

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

output:

NO

result:

ok Correct

Test #4:

score: 0
Accepted
time: 2ms
memory: 3516kb

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:

YES
? 249 1 233 233 176 176 80 80 186 186 25 25 38 38 91 91 213 213 8 8 106 106 139 139 163 163 134 134 3 3 162 162 73 73 90 90 232 232 48 48 29 29 244 244 142 142 145 145 40 40 28 28 147 147 216 216 120 120 165 165 205 205 20 20 62 62 50 50 127 127 210 210 36 36 226 226 41 41 12 12 107 107 77 77 47...

result:

ok OK 249 numbers

Test #5:

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

input:

250 1
159 6
156 104
218 66
172 38
158 142
37 143
171 240
53 204
139 103
152 177
213 231
91 93
75 77
39 125
239 28
196 237
185 209
40 219
43 114
129 222
162 247
140 23
48 35
184 215
186 155
58 178
178 98
82 91
238 164
33 54
127 165
60 151
2 7
160 223
189 247
50 209
189 205
81 49
237 180
88 156
225 20...

output:

YES
? 249 1 72 1 60 60 151 151 148 148 233 148 15 15 112 112 99 99 37 37 143 143 84 84 76 76 196 196 237 237 180 180 169 169 83 83 77 77 75 77 67 67 85 85 139 139 103 103 10 10 93 93 91 91 82 82 128 128 243 243 154 154 168 168 2 2 7 243 181 181 175 175 130 130 118 118 61 61 109 109 232 109 81 81 49 ...

result:

ok OK 249 numbers

Test #6:

score: 0
Accepted
time: 8ms
memory: 3908kb

input:

250 2
138 236
154 181
103 227
74 169
248 123
25 69
26 157
250 216
164 75
89 215
93 43
76 56
56 153
88 139
121 72
130 228
231 198
224 75
238 235
66 8
119 77
129 204
125 30
204 165
113 60
156 14
226 192
54 201
61 70
59 62
11 233
60 44
240 177
79 152
88 13
137 26
186 133
94 134
180 246
167 126
61 79
10...

output:

YES
? 249 232 101 88 2 131 3 64 4 88 5 29 6 221 143 72 7 184 8 87 9 43 134 88 10 51 11 115 12 67 13 108 14 229 15 70 16 64 92 23 17 52 32 9 18 46 19 78 20 176 21 215 59 174 22 135 23 224 50 1 24 29 25 157 137 157 161 127 26 248 27 224 28 84 29 75 30 29 33 99 31 104 32 84 33 51 34 56 35 163 36 90 37 ...

result:

ok OK 249 numbers

Test #7:

score: 0
Accepted
time: 0ms
memory: 3596kb

input:

250 3
208 175
120 43
87 33
248 90
78 198
220 229
177 17
239 236
142 187
48 35
233 214
53 14
12 184
126 227
77 113
202 41
152 12
108 19
69 136
168 163
176 57
179 110
159 211
28 103
102 137
180 156
165 101
87 150
89 132
38 151
242 49
81 165
127 185
41 127
115 215
11 29
216 92
215 34
145 75
141 45
235 ...

output:

NO

result:

ok Correct

Test #8:

score: -100
Wrong Answer
time: 2ms
memory: 3584kb

input:

250 4
116 188
148 118
200 249
230 192
208 143
189 157
22 2
23 212
140 107
67 215
46 18
38 111
135 129
22 19
210 158
224 171
31 10
36 113
48 238
146 225
184 147
52 85
189 191
247 244
68 6
234 70
45 204
221 186
100 172
192 173
108 7
217 87
56 80
63 117
193 47
153 181
52 65
166 102
133 121
151 117
243 ...

output:

NO

result:

wrong answer Expected "YES", but found "NO"
English 繁體中文 简体中文

服务器时间: 2025-01-20 21:14:07 | 开源项目