QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#127040 | #6634. Central Subset | 45645A# | WA | 8ms | 9808kb | C++14 | 2.0kb | 2023-07-19 12:32:58 | 2023-07-19 12:33:01 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
inline int read()
{
char ch;
while((ch=getchar())<'0'||ch>'9');
int res=ch-'0';
while((ch=getchar())>='0'&&ch<='9') res=res*10+ch-'0';
return res;
}
const int N=200100;
struct Edge{
int nxt,to;
}e[N<<1];
int h[N],e_num;
void add(int from,int to)
{
e[++e_num].nxt=h[from];
e[e_num].to=to;
h[from]=e_num;
}
int n,K;
struct BCJ{
int f[N];
void pre()
{
for(int i=1;i<=n;i++)
f[i]=i;
}
int find(int x){ return f[x]==x?x:(f[x]=find(f[x])); }
bool mrge(int x,int y)
{
x=find(x),y=find(y);
if(x==y) return 0;
f[x]=y;
return 1;
}
}B;
int vis[N],nxt[2][N],cnt[2],now;
int rt,mx,siz[N],all;
void getall(int u,int fa)
{
all++;siz[u]=1;
for(int i=h[u];i;i=e[i].nxt)
{
int v=e[i].to;
if(vis[v]||v==fa) continue;
getall(v,u);
siz[u]+=siz[v];
}
}
void dfs(int u,int fa)
{
int tmp=0;
for(int i=h[u];i;i=e[i].nxt)
{
int v=e[i].to;
if(vis[v]||v==fa) continue;
dfs(v,u);
if(siz[v]>tmp) tmp=siz[v];
}
if(all-siz[u]>tmp) tmp=all-siz[u];
if(tmp<mx) rt=u,mx=tmp;
}
void dfs_vis(int u,int dep)
{
if(dep>K) return void(nxt[now^1][++cnt[now^1]]=u);
vis[u]=1;
for(int i=h[u];i;i=e[i].nxt)
{
int v=e[i].to;
if(vis[v]) continue;
dfs_vis(v,dep+1);
}
}
int res[N],ans;
int main()
{
int T=read();
while(T--)
{
n=read();
int m=read();
B.pre();
e_num=0;
ans=0;
for(int i=1;i<=n;i++) vis[i]=h[i]=0;
for(int i=1;i<=m;i++)
{
int u=read(),v=read();
if(B.mrge(u,v)) add(u,v),add(v,u);
}
K=sqrt(n);
if(K*K!=n) K++;
nxt[now=0][cnt[0]=1]=1;
while(cnt[now])
{
cnt[now^1]=0;
for(int i=1;i<=cnt[now];i++)
{
all=0;
getall(nxt[now][i],0);
rt=nxt[now][i],mx=all;
dfs(nxt[now][i],0);
res[++ans]=rt;
dfs_vis(rt,0);
}
now^=1;
}
if(ans>K) printf("-1\n");
else
{
printf("%d\n",ans);
for(int i=1;i<=ans;i++) printf("%d ",res[i]);
printf("\n");
}
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 9808kb
input:
2 4 3 1 2 2 3 3 4 6 7 1 2 2 3 3 1 1 4 4 5 5 6 6 4
output:
1 3 1 4
result:
ok correct (2 test cases)
Test #2:
score: -100
Wrong Answer
time: 8ms
memory: 9752kb
input:
10000 15 14 13 12 5 4 9 8 11 12 15 14 10 9 14 13 2 3 2 1 6 5 10 11 3 4 7 6 8 7 6 5 2 1 2 4 4 6 2 3 3 5 10 9 8 3 9 4 5 6 5 10 3 2 5 4 2 7 1 2 4 3 2 1 2 1 2 1 2 1 9 8 9 8 5 4 1 2 6 5 3 4 3 2 7 8 7 6 2 1 1 2 14 13 3 10 5 6 2 9 11 4 2 3 2 1 8 7 13 6 5 4 5 12 6 7 4 3 7 14 16 15 2 3 2 1 6 10 6 9 6 4 9 11 ...
output:
3 8 2 14 1 2 1 4 1 2 1 2 3 5 9 1 1 2 1 5 2 6 16 1 2 3 11 3 19 1 4 1 4 1 8 1 2 3 8 14 2 1 2 1 2 1 4 1 2 1 3 1 3 1 5 1 5 1 2 3 8 2 14 1 2 1 5 1 2 1 2 3 11 19 3 1 3 1 5 2 6 16 1 2 1 4 1 3 1 4 3 5 20 21 1 2 3 7 1 12 1 2 1 4 1 3 1 2 2 6 1 1 3 1 4 1 5 1 2 ...
result:
wrong answer Integer -1 violates the range [1, 4] (test case 1829)