QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#604722 | #8757. 图 | UESTC_DebugSimulator# | WA | 75ms | 14528kb | C++17 | 2.9kb | 2024-10-02 13:30:23 | 2024-10-02 13:30:25 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define N 200010
#define int long long
int n,m,k,deg[N],d[N],f[N];
int p1,p2;
map<pair<int,int>,int> mp;
struct edge{
int u,v;
}a[N];
vector<vector<int>> g;
vector<vector<int>> ans;
int vis[N],ch;
int cmp(edge x,edge y)
{
return x.u<y.u||x.u==y.u&&x.v<y.v;
}
void dfs(int u)
{
if(ch) return;
if(u==p2)
{
ch=1;
vector<int> ans1;
int x=p2;
while(x!=p1)
{
ans1.push_back(x);
mp[{x,f[x]}]--;
mp[{f[x],x}]--;
x=f[x];
}
ans1.push_back(p1);
ans.push_back(ans1);
return;
}
for(auto v:g[u])
{
if(vis[v]) continue;
if(mp[{u,v}]==0) continue;
// for(int i=1;i<=mp[{u,v}];i++)
{
f[v]=u;
vis[u]=1;
dfs(v);
vis[u]=0;
}
}
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int T;
cin>>T;
while(T--)
{
cin>>n>>m;
g.resize(n+1);
g.clear();
mp.clear();
ans.clear();
for(int i=1;i<=n;i++)
{
d[i]=deg[i]=vis[i]=0;
}
if(m%(n-1)==0) k=m/(n-1);
else k=m/(n-1)+1;
for(int i=1;i<=m;i++)
{
cin>>a[i].u>>a[i].v;
if(a[i].u>a[i].v) swap(a[i].u,a[i].v);
}
if(m==1)
{
cout<<a[1].u<<" "<<a[1].v<<"\n";
cout<<"2 "<<a[1].u<<" "<<a[1].v<<"\n";
continue;
}
sort(a+1,a+m+1,cmp);
int x1=0,x2=0;
for(int i=1;i<=m;i++)
{
deg[a[i].u]++;deg[a[i].v]++;
if(a[i].u==a[i-1].u&&a[i].v==a[i-1].v)
{
mp[{a[i].u,a[i].v}]++;mp[{a[i].v,a[i].u}]++;
if(mp[{a[i].u,a[i].v}]>=k)
{
x1=a[i].u;
x2=a[i].v;
}
continue;
}
g[a[i].u].push_back(a[i].v);
g[a[i].v].push_back(a[i].u);
mp[{a[i].u,a[i].v}]=mp[{a[i].v,a[i].u}]=1;
}
if(x1)
{
cout<<x1<<" "<<x2<<"\n";
for(int i=1;i<=k;i++)
{
cout<<"2 "<<x1<<" "<<x2<<"\n";
}
continue;
}
queue<int> q;
for(int i=1;i<=n;i++)
{
d[i]=g[i].size();
if(g[i].size()==1)
{
q.push(i);
continue;
}
}
while(q.size())
{
int u=q.front();q.pop();
vis[u]=1;
for(auto v:g[u])
{
if(vis[v]) continue;
deg[v]=deg[v]-mp[{u,v}];
d[v]--;
if(d[v]==1) q.push(v);
break;
}
}
int mx=0;
p1=p2=0;
for(int i=1;i<=n;i++)
{
if(vis[i]) continue;
if(deg[i]>mx)
{
mx=deg[i];
p1=i;
}
}
mx=0;
for(int i=1;i<=n;i++)
{
if(vis[i]) continue;
if(deg[i]>mx&&i!=p1)
{
mx=deg[i];
p2=i;
}
}
// cout<<p1<<" "<<p2<<"\n";
// for(int i=1;i<=n;i++)
// {
// for(int j=1;j<=n;j++)
// {
//
// cout<<mp[{i,j}]<<" ";
// }
// cout<<"\n";
// }
for(int i=1;i<=k;i++)
{
ch=0;
dfs(p1);
}
if(ans.size()<k)
{
cout<<"-1\n";
continue;
}
cout<<p1<<" "<<p2<<"\n";
for(int i=0;i<ans.size();i++)
{
cout<<ans[i].size();
for(int j=ans[i].size()-1;j>=0;j--) cout<<" "<<ans[i][j];
cout<<"\n";
}
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 35ms
memory: 10380kb
input:
10000 2 20 1 2 1 2 2 1 1 2 1 2 2 1 1 2 2 1 1 2 1 2 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 1 2 2 1 2 20 2 1 2 1 2 1 2 1 2 1 1 2 1 2 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 2 20 1 2 2 1 1 2 1 2 2 1 2 1 1 2 1 2 2 1 2 1 1 2 1 2 1 2 1 2 2 1 1 2 1 2 1 2 2 1 2 1 2 20 1 2 2 1 2 1 1 2 1 2 1 2 2 1 1 2 2 ...
output:
1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 ...
result:
ok Answer correct. (10000 test cases)
Test #2:
score: 0
Accepted
time: 53ms
memory: 11944kb
input:
10000 5 20 2 1 2 5 5 3 3 1 4 5 1 4 4 3 4 5 3 5 5 4 2 3 5 2 3 4 3 5 1 4 4 3 4 2 2 1 1 3 5 1 5 20 4 2 1 3 1 2 4 5 2 4 3 1 5 3 5 1 4 5 4 3 2 4 1 4 4 3 5 2 1 2 3 5 1 5 4 1 3 4 4 3 5 20 1 4 1 3 1 5 5 1 4 5 3 4 4 5 2 3 1 2 2 4 4 5 4 5 2 4 2 5 4 2 4 3 4 2 2 5 2 1 3 1 5 20 2 5 2 3 4 5 4 2 3 4 2 1 5 4 2 5 2 ...
output:
3 4 4 3 1 2 4 5 3 1 2 5 4 5 3 2 5 1 4 2 3 4 2 3 4 4 1 2 4 1 2 4 1 3 4 2 1 3 4 2 1 4 4 2 5 1 4 2 3 4 1 2 2 4 2 2 4 2 2 4 2 2 4 2 2 4 4 2 1 3 4 4 2 1 3 4 3 2 1 4 4 2 3 5 4 2 2 4 2 3 2 2 3 2 2 3 2 2 3 2 2 3 2 2 3 1 5 4 1 2 3 5 3 1 3 5 4 1 4 2 5 4 1 4 2 5 3 1 4 5 2 5 5 2 1 3 4 5 4 2 1 3 5 3 2 3 5 3 2 3 ...
result:
ok Answer correct. (10000 test cases)
Test #3:
score: -100
Wrong Answer
time: 75ms
memory: 14528kb
input:
10000 10 20 9 4 8 6 2 10 2 9 7 10 4 6 9 4 2 1 4 7 1 5 7 2 4 1 5 9 7 6 8 2 9 4 5 9 9 8 7 3 2 4 10 20 3 8 8 9 8 7 9 2 3 10 9 3 8 1 9 4 8 9 4 7 7 5 5 10 1 3 3 4 3 7 3 8 3 9 1 4 3 6 2 4 10 20 7 6 8 10 3 8 2 8 4 8 4 8 4 6 4 1 1 7 4 6 5 9 5 2 4 7 10 9 6 7 10 5 2 4 4 1 3 2 4 9 10 20 2 1 9 8 7 6 2 10 9 5 4 ...
output:
4 9 2 4 9 2 4 9 2 4 9 3 8 6 3 1 4 2 9 8 4 3 4 7 8 2 3 8 4 8 4 4 2 3 8 2 4 8 2 4 8 2 9 4 2 1 5 9 5 2 4 3 8 9 6 2 6 4 10 5 9 2 4 7 2 3 9 6 1 7 4 4 2 3 10 4 4 2 5 6 4 6 7 4 6 2 1 7 4 6 3 2 7 2 6 7 7 9 6 7 1 3 4 6 9 5 7 2 1 4 9 3 7 3 9 6 7 2 6 7 2 6 7 2 6 7 8 5 5 8 4 3 1 5 2 8 5 5 8 6 3 2 5 6 10 2 6 10 ...
result:
wrong answer Integer -1 violates the range [1, 10] (test case 66)