QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#435628 | #8757. 图 | qzez | WA | 135ms | 6636kb | C++14 | 2.1kb | 2024-06-08 20:54:37 | 2024-06-08 20:54:37 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#ifdef DEBUG
#include"debug.h"
#else
#define debug(...) void()
#endif
#define all(x) (x).begin(),(x).end()
template<class T>
auto ary(T *a,int l,int r){
return vector<T>{a+l,a+1+r};
}
using ll=long long;
using ull=unsigned ll;
const int N=1e5+10;
int T,n,m,s,t;
vector<int>to[N];
vector<vector<int>>ans;
int fa[N],cnt[N],siz[N];
int find(int x){
return fa[x]==x?x:fa[x]=find(fa[x]);
}
void link(int x,int y,int w){
x=find(x),y=find(y);
if(x==y)cnt[x]+=w;
else cnt[y]+=cnt[x]+w,siz[y]+=siz[x],fa[x]=y;
}
vector<int>stk;
bool dfs(int u,int fa=0){
stk.push_back(u);
if(u==t)return ans.push_back(stk),1;
for(int v:to[u])if(v^fa){
if(dfs(v,u))return 1;
}
stk.pop_back();
return 0;
}
void solve(const vector<tuple<int,int,int>> &E,int k){
if(k==1){
auto [u,v,w]=E[0];
s=u,t=v,ans={{u,v}};
return;
}
iota(fa,fa+1+n,0);
fill(cnt,cnt+1+n,0);
fill(siz+1,siz+1+n,1);
for(auto [u,v,w]:E)link(u,v,w);
int rt=0,mx=0;
for(int i=1;i<=n;i++)if(fa[i]==i&&siz[i]>1){
int val=(cnt[i]-1)/(siz[i]-1)+1;
if(val>mx)mx=val,rt=i;
}
vector<tuple<int,int,int>>ne,ret;
for(auto [u,v,w]:E){
if(find(u)==rt)ne.push_back({u,v,w});
}
iota(fa,fa+1+n,0);
vector<pair<int,int>>cur;
for(auto [u,v,w]:ne){
int x=find(u),y=find(v);
if(x!=y){
fa[x]=y;
cur.push_back({u,v});
if(w>1)ret.push_back({u,v,w-1});
}else ret.push_back({u,v,w});
}
solve(ret,k-1);
for(auto [u,v]:cur){
to[u].push_back(v),to[v].push_back(u);
}
stk.clear(),dfs(s);
for(int i=1;i<=n;i++)to[i].clear();
}
void get(){
scanf("%d%d",&n,&m);
vector<tuple<int,int,int>>E(m);
for(auto &[u,v,w]:E){
scanf("%d%d",&u,&v),w=1;
if(u>v)swap(u,v);
}
sort(all(E));
int len=0;
for(int i=1;i<E.size();i++){
auto &[u1,v1,w1]=E[len];
auto &[u2,v2,w2]=E[i];
if(u1==u2&&v1==v2)w1++;
else E[++len]=E[i];
}
solve(E,(m-1)/(n-1)+1);
printf("%d %d\n",s,t);
for(const auto &x:ans){
printf("%ld",x.size());
for(int y:x)printf(" %d",y);
puts("");
}
}
int main(){
for(scanf("%d",&T);T--;)get();
return 0;
}
#ifdef DEBUG
#include"debug.hpp"
#endif
详细
Test #1:
score: 100
Accepted
time: 135ms
memory: 6152kb
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: 58ms
memory: 6172kb
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 2 3 4 2 3 4 3 3 2 4 3 3 1 4 3 3 1 4 2 4 2 2 4 2 2 4 2 2 4 3 2 1 4 3 2 1 4 2 4 2 2 4 2 2 4 2 2 4 2 2 4 3 2 1 4 3 4 2 3 4 2 3 4 3 3 2 4 4 3 1 2 4 3 3 1 4 1 5 2 1 5 2 1 5 2 1 5 2 1 5 2 1 5 2 5 2 2 5 2 2 5 4 2 4 1 5 4 2 3 1 5 3 2 1 5 3 4 2 3 4 3 3 2 4 3 3 2 4 4 3 1 2 4 3 3 1 4 2 4 2 2 4 2 2 4 2 2 4 ...
result:
ok Answer correct. (10000 test cases)
Test #3:
score: -100
Wrong Answer
time: 52ms
memory: 6636kb
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 4 4 1 2 9 3 8 2 3 8 2 3 8 3 3 1 8 4 8 2 4 8 2 4 8 3 4 2 8 5 9 2 5 9 2 5 9 4 5 1 2 9 3 10 2 3 10 3 3 2 10 5 3 2 7 1 10 3 10 2 3 10 2 3 10 4 3 2 1 10 4 7 2 4 7 3 4 3 7 3 4 1 7 5 6 2 5 6 2 5 6 6 5 1 2 9 4 6 6 10 2 6 10 5 6 8 5 2 10 4 6 3 2 10 5 9 2 5 9 2 5 9 5 5 8 1 4 9 4 8 2 4 8 2 4 8 ...
result:
FAIL No edge cross. (test case 292)