QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#865226 | #9866. Extracting Weights | lw22005 | WA | 1ms | 3840kb | C++14 | 1.4kb | 2025-01-21 16:12:07 | 2025-01-21 16:12:07 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int N=310;
int n,k,a,b,cnt,h[N],c[N],d[N];
bitset<310>tmp,s[N],t[N],t1[N];
struct AB{
int x,y,n;
}l[N*2];
void in(int x,int y){
l[++cnt].x=x,l[cnt].y=y;
l[cnt].n=h[x],h[x]=cnt;
}
void add(int p,int rt){
tmp=s[p];
for(int i=n;i>=1;i--){
if(!s[p][i])continue;
else{
if(t[i][i]){
s[p]^=t[i];
if(s[p]==s[0])break;
}else{
t[i]=s[p],t1[i]=tmp;
c[i]=p,d[i]=rt;
break;
}
}
}
}
void dfs(int a,int p,int st,int rt){
int b;
s[a]=s[p],s[a].set(a);
if(st==k){
add(a,rt);
return ;
}
for(int i=h[a];i;i=l[i].n){
b=l[i].y;
if(b==p)continue;
dfs(b,a,st+1,rt);
}
}
int main(){
scanf("%d%d",&n,&k);
for(int i=1;i<n;i++){
scanf("%d%d",&a,&b);
in(a,b),in(b,a);
}
s[0].reset();
for(int i=1;i<=n;i++){
dfs(i,0,0,i);
}
t[1].set(1),t1[1]=t[1];
for(int i=1;i<=n;i++){
if(t[i][i]==0){
cout<<"NO"<<endl;
return 0;
}
}
cout<<"YES"<<endl;
cout<<"? "<<n-1<<' ';
for(int i=2;i<=n;i++){
cout<<c[i]<<' '<<d[i]<<' ';
}
cout<<endl;
for(int i=2;i<=n;i++){
cin>>c[i];
}
for(int i=n;i>=1;i--){
for(int j=i-1;j>=1;j--){
if(t1[j][i])t1[j]^=t1[i],c[j]^=c[i];
}
}
for(int i=2;i<=n;i++){
for(int j=1;j<i;j++){
if(t1[i][j])c[i]^=c[j];
}
}
cout<<"! ";
for(int i=2;i<=n;i++)cout<<c[i]<<' ';
cout<<endl;
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3840kb
input:
4 1 1 2 2 3 2 4 1 3 2
output:
YES ? 3 2 1 3 2 4 2 ! 1 2 3
result:
ok OK 3 numbers
Test #2:
score: 0
Accepted
time: 0ms
memory: 3840kb
input:
5 2 1 2 2 3 3 4 3 5 4 1 2 3
output:
YES ? 4 5 4 3 1 4 2 5 2 ! 4 5 3 2
result:
ok OK 4 numbers
Test #3:
score: 0
Accepted
time: 0ms
memory: 3840kb
input:
6 2 1 2 2 3 3 4 4 5 4 6
output:
NO
result:
ok Correct
Test #4:
score: 0
Accepted
time: 1ms
memory: 3840kb
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 248 203 233 176 207 195 230 215 156 122 16 7 163 139 245 140 231 198 129 99 205 165 217 174 250 220 225 214 16 4 208 126 197 18 212 185 210 127 249 143 218 22 227 158 243 169 213 91 173 26 27 21 145 142 232 90 30 11 238 196 115 114 204 100 219 178 172 168 226 41 128 37 38 25 194 96 40 28 4...
result:
ok OK 249 numbers
Test #5:
score: 0
Accepted
time: 0ms
memory: 3712kb
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 237 196 237 180 243 154 228 222 216 207 7 2 204 194 116 79 93 10 231 213 179 113 201 97 184 14 151 148 225 205 240 171 56 18 223 206 191 179 239 162 158 142 238 164 230 24 139 103 56 26 194 27 106 80 182 129 238 68 221 141 115 65 214 54 220 131 35 31 245 135 112 99 186 155 159 125 219 40 8...
result:
ok OK 249 numbers
Test #6:
score: -100
Wrong Answer
time: 1ms
memory: 3840kb
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 173 134 153 63 200 92 139 13 84 33 121 95 184 112 104 52 88 10 131 56 230 210 173 13 188 108 155 152 172 69 151 17 141 18 217 105 236 144 166 114 215 146 187 23 227 135 117 25 137 46 153 76 224 28 25 6 232 50 172 31 104 32 33 29 51 34 189 76 193 111 195 93 247 85 87 39 166 40 123 76 182 42...
result:
wrong answer Wrong answer in node 30, expected "1043155115", but found "1043155053".