QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#490969 | #8757. 图 | maojun | WA | 90ms | 30588kb | C++23 | 1.5kb | 2024-07-25 16:53:37 | 2024-07-25 16:53:39 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int n,m,k,u[N],v[N];
#define eb emplace_back
struct Graph{
map<int,int>V;
int idx=0;vector<int>fa,id;
vector<pair<int,int>>E;
int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}
int gnew(int x){id.eb(x);fa.eb(idx);V[x]=idx;return idx++;}
void ins(int u,int v){
u=V.find(u)==V.end()?gnew(u):V[u];
v=V.find(v)==V.end()?gnew(v):V[v];
fa[find(u)]=v;E.eb(u,v);
}
bool chk(int u,int v){
if(V.find(u)==V.end())return false;u=V[u];
if(V.find(v)==V.end())return false;v=V[v];
return find(u)==find(v);
}
void clr(){idx=0;V.clear();fa.clear();id.clear();E.clear();}
vector<int>fpath(int x,int y){
vector<int>f(idx),g[idx];x=V[x];y=V[y];
for(auto[u,v]:E){g[u].eb(v);g[v].eb(u);}
function<void(int,int)>dfs=[&](int u,int fath){
f[u]=fath;for(int v:g[u])if(v^fath)dfs(v,u);
};dfs(x,-1);
vector<int>p;for(int u=y;~u;u=f[u])p.eb(id[u]);return p;
}
}G[N];
inline void solve(){
// puts("------");
scanf("%d%d",&n,&m);k=(m+n-2)/(n-1);
for(int i=1;i<=m;i++)scanf("%d%d",&u[i],&v[i]);
for(int i=1;i<=k;i++)G[i].clr();
for(int i=1;i<=m;i++){
int l=1,r=k,mid;
while(l<r)G[mid=l+r>>1].chk(u[i],v[i])?l=mid+1:r=mid;
if(l==k){
printf("%d %d\n2 %d %d\n",u[i],v[i],u[i],v[i]);
for(int j=1;j<k;j++){
vector<int>P=G[j].fpath(u[i],v[i]);
printf("%d",P.size());for(int x:P)printf(" %d",x);puts("");
}
}else G[l].ins(u[i],v[i]);
}
}
int main(){
int T;scanf("%d",&T);
while(T--)solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 90ms
memory: 30588kb
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:
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 1 2 2 1 2 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 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 ...
result:
FAIL Begin in s. (test case 1)