QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#879919#9866. Extracting Weightsfrankly6TL 0ms3456kbC++172.9kb2025-02-02 18:12:172025-02-02 18:12:18

Judging History

This is the latest submission verdict.

  • [2025-02-02 18:12:18]
  • Judged
  • Verdict: TL
  • Time: 0ms
  • Memory: 3456kb
  • [2025-02-02 18:12:17]
  • Submitted

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 

result: