QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#491498#8757. 图FffooooTL 0ms0kbC++142.5kb2024-07-25 19:58:332024-07-25 19:58:34

Judging History

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

  • [2024-07-25 19:58:34]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:0kb
  • [2024-07-25 19:58:33]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
int mian(); int main() { return mian(); }

const int N = 1e5 + 15, M = 2e5 + 25;
int n, m, k;

int id(const int i, const int j) { return i + (j - 1) * n; }
struct UF {
	int fa[M], siz[M];
	void init_fa() { for(int i = 1; i < M; ++i) fa[i] = i, siz[i] = 1; }
	int get(const int x) { if( x == fa[x] ) return x; return fa[x] = get(fa[x]); }
	void us(int u, int v) {
		u = get(u); v = get(v);
		if( siz[u] < siz[v] ) swap(u, v);
		siz[u] += siz[v]; fa[v] = u;
	}
}uf;

vector<int> eg[M];
void add(const int u, const int v) { eg[u].push_back(v); eg[v].push_back(u); }

int fa[N], dep[N];
void dfs_tree(const int u, const int dad) {
	fa[u] = dad; dep[u] = dep[dad] + 1;
	for(auto v : eg[u]) if( v != dad ) dfs_tree(v, u);
}

void solvp(const int u, const int v) {
	printf("%d %d\n", u, v);
	for(int now = 1; now <= k; ++now) {
		dfs_tree( id(v, now), 0 );
		printf("%d ", dep[ id(u, now) ]);
		int x = id(u, now);
		while( x != 0 ) printf("%d ", ( x - 1 ) % n + 1), x = fa[x];
		puts("");
	}
}
void solve() {
	scanf("%d%d", &n, &m);
	k = ceil( (double)m / (double)(n - 1) );
	uf.init_fa();
	for(int i = 1; i <= id(n, k); ++i) eg[i].clear();
	for(int i = 1, u, v; i <= m; ++i) {
		scanf("%d%d", &u, &v);
		int l = 1, r = k, now = k + 1;
		while( l <= r ) {
			const int mid = (l + r) >> 1;//只能二分 
			if( uf.get( id(u, mid) ) != uf.get( id(v, mid) ) ) r = mid - 1, now = mid;
			else l = mid + 1;
		}
		if( now <= k ) add( id(u, now), id(v, now) ), uf.us( id(u, now), id(v, now) );
	}
	for(int u = 1; u <= n; ++u) if( uf.get( id(u, k) ) != id(u, k) ) return (void) solvp( u, uf.get( id(u, k) ) % n );
	puts("-1");
}
int mian() {
	int T; scanf("%d", &T);
	while( T-- ) solve();
	return 0;
} /*
给定一张 $n$ 点 $m$ 条边的图,求一个点对 $(u,v)$ 满足他们之间有 $k=\lceil \dfrac{m}{n-1} \rceil$ 条边不相交的路径 
$n\le 10^5, m\le 2\times 10^5$ 
$1s, 512MB$

考虑直接构造出 $k$ 条路经 
那么不妨直接构造出来 $k$ 层图,使得这 $k$ 层图中,任意两个点的路径在 $k$ 张图上互不相交 
也就是每一条边只属于一张图。 
那么对于每一层图,如果要加入的边 $(u,v)$ 已经联通,那么就加入到下一层图中,一直知道第一个不连通的图中 
那么,一层至多有 $n-1$ 条边(一棵树,全联通),于是至少有 $\lceil \dfrac{m}{n-1} \rceil=k$ 层图 
找到第 $k$ 层的任意一队点并在下面的层中找到对应的路径即可 
*/

詳細信息

Test #1:

score: 0
Time Limit Exceeded

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 0
0 1 
0 1 
0 1 
0 1 
0 1 
0 1 
0 1 
0 1 
0 1 
0 1 
0 1 
0 1 
0 1 
0 1 
0 1 
0 1 
0 1 
0 1 
0 1 
0 1 
2 1
3 2 1 
3 2 1 
3 2 1 
3 2 1 
3 2 1 
3 2 1 
3 2 1 
3 2 1 
3 2 1 
3 2 1 
3 2 1 
3 2 1 
3 2 1 
3 2 1 
3 2 1 
3 2 1 
3 2 1 
3 2 1 
3 2 1 
3 2 1 
1 0
2 1 
2 1 
2 1 
2 1 
2 1 
2 1 
2 1 
2 1 
2 1 
2 1...

result: