QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#879919 | #9866. Extracting Weights | frankly6 | TL | 0ms | 3456kb | C++17 | 2.9kb | 2025-02-02 18:12:17 | 2025-02-02 18:12:18 |
Judging History
answer
#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
#include<bitset>
typedef long long ll;
using namespace std;
const int MX=255;
int T, N, K;
int head[MX], cnt=0;
int son[MX], siz[MX], fa[MX], dep[MX], top[MX];
int w[MX], num, ans[MX];
bitset<MX> m[MX];
vector<int> ask;
int read()
{
int r=0, f=1; char ch=getchar();
while(ch<'0'||ch>'9') {if(ch=='-') f=-1; ch=getchar();}
while(ch>='0'&&ch<='9') {r=r*10+ch-'0'; ch=getchar();}
return r*f;
}
struct edge{int nxt, to;}e[2*MX];
inline void ae(int u, int v){e[++cnt].to=v; e[cnt].nxt=head[u]; head[u]=cnt;}
void dfs(int x, int f, int D)
{
fa[x]=f; dep[x]=D; siz[x]=1;
for(int i=head[x];i;i=e[i].nxt)
{
int y=e[i].to;
if(y==f) continue;
dfs(y,x,D+1);
siz[x]+=siz[y];
if(siz[y]>siz[son[x]]) son[x]=y;
}
}
void dfs2(int x, int topf)
{
top[x]=topf;
if(!son[x]) return;
dfs2(son[x],topf);
for(int i=head[x];i;i=e[i].nxt)
{
int y=e[i].to;
if(y==son[x]||y==fa[x]) continue;
dfs2(y,y);
}
}
int lca(int x, int y)
{
while(top[x]!=top[y])
{
if(dep[top[x]]<dep[top[y]]) swap(x,y);
x=fa[top[x]];
}
return dep[x]<dep[y]?x:y;
}
int dis(int x, int y) {return dep[x]+dep[y]-2*dep[lca(x,y)];}
void path(int x, int y)
{
int l=lca(x,y);
while(x!=l)
{
m[num][x]=1;
x=fa[x];
}
while(y!=l)
{
m[num][y]=1;
y=fa[y];
}
m[num][l]=1;
}
int main()
{
// freopen("testdata.in","r",stdin);
N=read(); K=read();
for(int i=1;i<N;i++)
{
int u=read(), v=read();
ae(u,v); ae(v,u);
}
dfs(1,0,1);
dfs2(1,1);
ask.emplace_back(N-1);
m[++num][1]=1; ans[1]=0;
for(int i=1;i<=N;i++)
{
for(int j=i+1;j<=N;j++)
{
if(dis(i,j)!=K) continue;
num++; path(i,j);
ask.emplace_back(i);
ask.emplace_back(j);
if(num==N) break;
}
}
if(num<N) cout << "NO\n";
else
{
cout << "YES\n? ";
for(auto u:ask) cout << u << " "; cout << '\n';
cout.flush();
for(int i=2;i<=N;i++) ans[i]=read();
for(int i=1;i<=N;i++)
{
if(m[i][i]==0)
{
for(int j=i+1;j<=N;j++)
{
if(m[i][i]==0&&m[j][i]==1)
{
swap(m[i],m[j]);
swap(ans[i],ans[j]);
break;
}
}
}
for(int j=1;j<=N;j++)
{
if(i==j||m[j][i]==0) continue;
m[j]=m[j]^m[i];
ans[j]^=ans[i];
}
}
cout << "! ";
for(int i=2;i<=N;i++) cout << ans[i] << " "; cout << '\n';
}
return (0-0);
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3456kb
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: 0ms
memory: 3456kb
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: -100
Time Limit Exceeded
input:
6 2 1 2 2 3 3 4 4 5 4 6
output:
YES ? 5 1 3 2 4 3 5 3 6 5 6