oj.uz

Submission #711751

# Submission time Handle Problem Language Result Execution time Memory
711751 2023-03-17T12:14:24 Z vjudge1 Multidrink (POI13_mul) C++17
100 / 100
 406 ms 101012 KB 
#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.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 47220 KB Output is correct
2 Correct 23 ms 47296 KB Output is correct
3 Correct 23 ms 47252 KB Output is correct
4 Correct 27 ms 47180 KB Output is correct
5 Correct 24 ms 47188 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 47252 KB Output is correct
2 Correct 22 ms 47256 KB Output is correct
3 Correct 23 ms 47272 KB Output is correct
4 Correct 26 ms 47196 KB Output is correct
5 Correct 24 ms 47324 KB Output is correct

Subtask #3
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 47188 KB Output is correct
2 Correct 22 ms 47212 KB Output is correct
3 Correct 24 ms 47264 KB Output is correct
4 Correct 23 ms 47188 KB Output is correct
5 Correct 26 ms 47296 KB Output is correct
6 Correct 23 ms 47208 KB Output is correct

Subtask #4
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 47288 KB Output is correct
2 Correct 29 ms 47236 KB Output is correct
3 Correct 25 ms 47260 KB Output is correct
4 Correct 25 ms 47324 KB Output is correct
5 Correct 23 ms 47256 KB Output is correct
6 Correct 23 ms 47304 KB Output is correct

Subtask #5
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 47220 KB Output is correct
2 Correct 25 ms 47268 KB Output is correct
3 Correct 24 ms 47188 KB Output is correct
4 Correct 28 ms 47268 KB Output is correct
5 Correct 28 ms 47248 KB Output is correct
6 Correct 24 ms 47268 KB Output is correct

Subtask #6
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 47216 KB Output is correct
2 Correct 24 ms 47188 KB Output is correct
3 Correct 25 ms 47260 KB Output is correct
4 Correct 26 ms 47188 KB Output is correct
5 Correct 26 ms 47188 KB Output is correct
6 Correct 27 ms 47308 KB Output is correct

Subtask #7
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 47248 KB Output is correct

Subtask #8
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 47204 KB Output is correct

Subtask #9
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 47220 KB Output is correct

Subtask #10
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 47272 KB Output is correct

Subtask #11
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 47436 KB Output is correct

Subtask #12
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 47260 KB Output is correct

Subtask #13
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 47292 KB Output is correct

Subtask #14
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 47548 KB Output is correct

Subtask #15
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 47512 KB Output is correct
2 Correct 26 ms 47232 KB Output is correct

Subtask #16
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 54240 KB Output is correct

Subtask #17
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 54348 KB Output is correct

Subtask #18
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 52016 KB Output is correct
2 Correct 24 ms 47184 KB Output is correct

Subtask #19
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 355 ms 78084 KB Output is correct

Subtask #20
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 335 ms 78012 KB Output is correct

Subtask #21
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 406 ms 80732 KB Output is correct
2 Correct 366 ms 81408 KB Output is correct

Subtask #22
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 402 ms 100348 KB Output is correct
2 Correct 279 ms 101012 KB Output is correct