Submission #711751

#	Time	Username	Problem	Language	Result	Execution time	Memory
711751		vjudge1	Multidrink (POI13_mul)	C++17	100 / 100	406 ms	101012 KiB

mul

#include <bits/stdc++.h>
#define rep(i, x, y) for (int i = (x); i <= (y); i+=1)
#define epr(i, x) for (int i = head[x]; i; i = nxt[i])
#define per(i, x, y) for (int i = (x); i >= (y); i-=1)
#define DC int T = gi <int> (); while (T--)
#define eb emplace_back
#define ep emplace
#define pb push_back
#define mp make_pair
#define fi first
#define se second

using namespace std;

typedef long long LL;
typedef unsigned long long ULL;
typedef pair <int, int> PII;
typedef pair <LL, int> PLI;
typedef pair <int, LL> PIL;
typedef pair <LL, LL> PLL;

template <typename T>
inline T gi()
{
	T x = 0, f = 1; char c = getchar();
	while (c < '0' || c > '9') {if (c == '-') f = -1; c = getchar();}
	while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
	return f * x;
}

template <typename T, typename U> inline void chkmax(T &x, const U &y) {x = x > y ? x : y;}
template <typename T, typename U> inline void chkmin(T &x, const U &y) {x = x < y ? x : y;}

const int N = 2000003, M = N << 1;

int n;
vector <int> g[N];
int deg[N];
bool f[N][3], h[N][2], vis[N];
int stk[N], tp, a[N], m;
bool fl;
vector <int> ans;

void find_path(int u, int f)
{
	stk[++tp] = u; if (u == n) {m = tp; rep(i, 1, tp) a[i] = stk[i], vis[a[i]] = 1; fl = 1; return;}
	for (auto v : g[u]) if (v ^ f) {find_path(v, u); if (fl) return;}
	--tp;
}

void dfs_f(int u, int fa)
{
	bool is_leaf = 1;
	int c1 = 0, c2 = 0;
	f[u][0] = f[u][1] = f[u][2] = 1;
	for (auto v : g[u])
		if ((v ^ fa) && !vis[v])
		{
			dfs_f(v, u);
			if (!f[v][0]) {if (!f[v][1]) f[u][1] = 0; else if (++c1 > 1) f[u][1] = 0;}
			if (!f[v][0]) {if (!f[v][1]) f[u][2] = 0; else if (++c2 > 2) f[u][2] = 0;}
			is_leaf = 0;
		}
	if (is_leaf) f[u][1] = f[u][2] = 0; else f[u][0] = 0;
}

void find_f(int u, int i, int fa = 0)
{
	if (!i) ans.eb(u);
	else if (i == 1)
	{
		ans.eb(u);
		for (auto v : g[u]) if ((v ^ fa) && !vis[v]) if (f[v][1]) find_f(v, 3, u);
		for (auto v : g[u]) if ((v ^ fa) && !vis[v]) if (f[v][0]) find_f(v, 0, u);
	}
	else if (i == 2)
	{
		int v1 = 0, v2 = 0;
		for (auto v : g[u]) if ((v ^ fa) && !vis[v]) if (f[v][1]) {if (!v1) v1 = v; else v2 = v;}
		if (!v2) return find_f(u, 1, fa);
		find_f(v1, 1, u), ans.eb(u), find_f(v2, 3, u);
		for (auto v : g[u]) if ((v ^ fa) && !vis[v]) if (f[v][0]) find_f(v, 0, u);
	}
	else
	{
		for (auto v : g[u]) if ((v ^ fa) && !vis[v]) if (f[v][0]) find_f(v, 0, u);
		for (auto v : g[u]) if ((v ^ fa) && !vis[v]) if (f[v][1]) find_f(v, 1, u);
		ans.eb(u);
	}
}

void find_h(int i, int j)
{
	if (i == 1) return find_f(1, j ^ 1);
	int u = a[i];
	if (j == 0)
	{
		if (h[i - 1][0] & f[u][1]) {find_h(i - 1, 0), find_f(u, 1); return;}
		if (h[i - 1][1] & f[u][1]) {find_h(i - 1, 1), find_f(u, 1); return;}
		find_h(i - 1, 1), find_f(u, 2);
	}
	else
	{
		if (h[i - 1][0] & f[u][0]) {find_h(i - 1, 0), find_f(u, 0); return;}
		if (h[i - 1][1] & f[u][0]) {find_h(i - 1, 1), find_f(u, 0); return;}
		find_h(i - 1, 1), find_f(u, 3);
	}
}

int main()
{
	n = gi <int> (); rep(_, 1, n - 1) {int u = gi <int> (), v = gi <int> (); g[u].eb(v), g[v].eb(u);}
	find_path(1, 0); rep(i, 1, m) dfs_f(a[i], 0);
	h[1][0] = f[1][1], h[1][1] = f[1][0];
	rep(i, 2, m)
	{
		int u = a[i];
		h[i][0] |= h[i - 1][0] & f[u][1];
		h[i][0] |= h[i - 1][1] & (f[u][1] | f[u][2]);
		h[i][1] |= h[i - 1][0] & f[u][0];
		h[i][1] |= h[i - 1][1] & (f[u][0] | f[u][1]);
	}
	if (!h[m][1]) return puts("BRAK"), !!0;
	find_h(m, 1);
	for (auto x : ans) printf("%d\n", x);
	return !!0;
}

• Subtask 1: 4 / 4
• Subtask 2: 4 / 4
• Subtask 3: 4 / 4
• Subtask 4: 4 / 4
• Subtask 5: 4 / 4
• Subtask 6: 4 / 4
• Subtask 7: 4 / 4
• Subtask 8: 4 / 4
• Subtask 9: 4 / 4
• Subtask 10: 4 / 4
• Subtask 11: 5 / 5
• Subtask 12: 5 / 5
• Subtask 13: 5 / 5
• Subtask 14: 5 / 5
• Subtask 15: 5 / 5
• Subtask 16: 5 / 5
• Subtask 17: 5 / 5
• Subtask 18: 5 / 5
• Subtask 19: 5 / 5
• Subtask 20: 5 / 5
• Subtask 21: 5 / 5
• Subtask 22: 5 / 5