QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#804729 | #9866. Extracting Weights | ucup-team1134# | RE | 1ms | 3752kb | C++23 | 4.0kb | 2024-12-08 03:01:26 | 2024-12-08 03:01:27 |
Judging History
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;
}
}
详细
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 ...