QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#815676 | #9866. Extracting Weights | Nana7 | WA | 9ms | 9380kb | C++14 | 2.3kb | 2024-12-15 16:23:40 | 2024-12-15 16:23:42 |
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];
bitset<N> a[N*N];
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]);
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>
I void solve() {
cin>>n>>k;
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.m=n;
vector<pii> query;
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;
if(ck.Gauss()) {
cout<<"NO"<<endl;
cout.flush();
return ;
}
int sz= query.size();
cout<<"YES"<<endl;
cout.flush();
cout<<"? "<<sz<<' ';
for(auto &t:query) {
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();
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 9380kb
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: 3ms
memory: 9348kb
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: 0ms
memory: 9352kb
input:
6 2 1 2 2 3 3 4 4 5 4 6
output:
NO
result:
ok Correct
Test #4:
score: 0
Accepted
time: 9ms
memory: 9340kb
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 2 195 2 197 3 134 3 162 4 16 4 72 5 140 5 240 6 156 6 207 7 16 7 99 8 106 8 213 9 56 9 110 10 81 10 126 11 30 11 128 12 41 12 107 13 174 13 218 14 121 14 235 15 223 15 242 17 161 17 177 18 173 18 197 19 171 19 181 20 62 20 205 21 27 21 249 22 102 22 218 23 153 23 182 24 78 24 92 25 3...
result:
ok OK 249 numbers
Test #5:
score: 0
Accepted
time: 7ms
memory: 9328kb
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 60 1 72 2 7 2 168 3 237 4 92 4 93 5 56 5 166 6 159 6 230 8 184 8 214 9 106 10 93 10 103 11 155 12 100 12 179 13 194 13 208 14 184 14 219 15 112 15 137 15 148 16 70 16 86 17 101 17 225 18 56 19 68 19 158 20 119 20 160 20 217 21 131 22 142 23 140 23 245 24 117 24 230 25 139 25 242 26 56 26...
result:
ok OK 249 numbers
Test #6:
score: -100
Wrong Answer
time: 7ms
memory: 9336kb
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 ? 321 1 24 1 120 2 10 2 88 3 56 3 131 3 214 4 64 4 106 5 88 6 25 6 29 6 117 7 72 7 160 7 205 8 184 9 18 9 39 9 87 9 141 10 88 10 93 10 94 11 34 11 51 11 63 12 115 13 67 13 109 13 139 13 173 13 180 14 108 14 171 14 188 14 249 15 229 15 241 16 70 16 79 16 204 17 23 17 151 17 187 18 45 18 100 18 14...
result:
wrong answer Integer parameter [name=q] equals to 321, violates the range [1, 250]