QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#491525 | #8757. 图 | sumi007 | RE | 0ms | 0kb | C++14 | 1.6kb | 2024-07-25 20:06:10 | 2024-07-25 20:06:10 |
answer
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pii pair<int,int>
#define pb push_back
const int N = 5e5+5;
int n,m,K,top,stk[N];
vector<int> path,e[N];
struct dsu{
vector<int> fa;
void init(){
fa.pb(0);
for(int i=1;i<=n;i++) fa.pb(i);
}
int find(int u){
if(u==fa[u]) return fa[u];
return fa[u] = find(fa[u]);
}
void merge(int u,int v){
u = find(u),v = find(v);
if(u==v) return ;
fa[u] = v;
}
};
bool get_path(int u,int fa,int ed){
stk[++top] = u;
if(u==ed){
while(top) path.pb(stk[top--]);
reverse(path.begin(),path.end());
return 1;
}
for(int v:e[u]){
if(v==fa) continue;
if(get_path(v,u,ed)) return 1;
}
top--;
return 0;
}
void solve(){
cin >> n >> m;K = (m+n-1)/(n-1);
vector<dsu> s(K+1);
vector<vector<pii >> g(K+1);
for(int i=1;i<=K;i++) s[i].init();
for(int i=1,u,v;i<=m;i++){
cin >> u >> v;
int l = 1,r = K,pos = -1;
while(l<=r){
int mid = (l+r)>>1;
if(s[mid].find(u) != s[mid].find(v)){
pos = mid;
r = mid-1;
}else{
l = mid+1;
}
}
if(pos==-1) break;
s[pos].merge(u,v),g[pos].pb({u,v});
}
int x = g[K][0].fi,y = g[K][0].se;
cout << x << ' ' << y << '\n';
for(int i=1;i<=K;i++){
top = 0,path.clear();
for(int u=1;u<=n;u++) e[u].clear();
for(pii r:g[i]) e[r.fi].pb(r.se),e[r.se].pb(r.fi);
get_path(x,0,y);
cout << path.size() << ' ';
for(int u:path) cout << u << ' ';
cout << '\n';
}
}
int main(){
cin.tie(0),cout.tie(0);
ios::sync_with_stdio(0);
int T;cin >> T;
while(T--) solve();
return 0;
}
詳細信息
Test #1:
score: 0
Runtime Error
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 ...