QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#490969#8757. 图maojunWA 90ms30588kbC++231.5kb2024-07-25 16:53:372024-07-25 16:53:39

Judging History

你现在查看的是最新测评结果

  • [2024-07-25 16:53:39]
  • 评测
  • 测评结果:WA
  • 用时:90ms
  • 内存:30588kb
  • [2024-07-25 16:53:37]
  • 提交

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)