【Codeforces 782E】Underground Lab

相关链接

题目传送门：http://codeforces.com/contest/782/problem/E

吐槽

没有看懂题，于是跑去问Menci题意
结果Menci先说做法，后说题意 _(:з」∠)_
强行把我带上了紫 *★,°*:.☆(￣▽￣)/$:*.°★* 。

解题报告

我们发现这个$\lceil \ \rceil$和$2n$非常妙啊！
于是乎，我们先搞出欧拉序，然后分成$k$段输出就可以了

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 400009;

int n,m,k,tot,vis[N],head[N],nxt[N],to[N],que[N];

inline int read() {
	char c=getchar(); int f=1,ret=0;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret * f;
}

inline void Add_Edge(int u, int v) {
	static int E = 1;
	to[++E] = v; nxt[E] = head[u]; head[u] = E;
	to[++E] = u; nxt[E] = head[v]; head[v] = E;
}

void DFS(int w) {
	vis[w] = 1; que[++tot] = w;
	for (int i=head[w];i;i=nxt[i]) {
		if (!vis[to[i]]) {
			DFS(to[i]);
			que[++tot] = w;
		}
	} 
}

int main() {
	n = read(); m = read(); k = read();
	for (int i=1;i<=m;i++) {
		Add_Edge(read(), read());
	}
	DFS(1);
	for (int i=1,cur=1,c=ceil(2.0*n/k);i<=k;i++) {
		if (cur > tot) puts("1 1"); 
		else {
			if (tot-cur+1 >= c) {
				printf("%d ",c);
				for (int j=1;j<=c;j++) printf("%d ",que[cur++]);
				puts("");
			} else {
				printf("%d ",tot-cur+1);
				for (int j=cur;j<=tot;j++) printf("%d ",que[j]);
				puts("");
			}
		}
	}
	return 0;
}