Submission #768387

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
768387	2023-06-28T04:21:30 Z	marvinthang	Split the Attractions (IOI19_split)	C++17	100 / 100	108 ms	32752 KB

split

/*************************************
*    author: marvinthang             *
*    created: 28.06.2023 10:35:00    *
*************************************/

#include "split.h"
#include <bits/stdc++.h>

using namespace std;

#define                  fi  first
#define                  se  second
#define                left  ___left
#define               right  ___right
#define                TIME  (1.0 * clock() / CLOCKS_PER_SEC)
#define             MASK(i)  (1LL << (i))
#define           BIT(x, i)  ((x) >> (i) & 1)
#define  __builtin_popcount  __builtin_popcountll
#define              ALL(v)  (v).begin(), (v).end()
#define           REP(i, n)  for (int i = 0, _n = (n); i < _n; ++i)
#define          REPD(i, n)  for (int i = (n); i--; )
#define        FOR(i, a, b)  for (int i = (a), _b = (b); i < _b; ++i) 
#define       FORD(i, b, a)  for (int i = (b), _a = (a); --i >= _a; ) 
#define       FORE(i, a, b)  for (int i = (a), _b = (b); i <= _b; ++i) 
#define      FORDE(i, b, a)  for (int i = (b), _a = (a); i >= _a; --i) 
#define        scan_op(...)  istream & operator >> (istream &in, __VA_ARGS__ &u)
#define       print_op(...)  ostream & operator << (ostream &out, const __VA_ARGS__ &u)
#ifdef LOCAL
    #include "debug.h"
#else
    #define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
    #define DB(...) 23
    #define db(...) 23
    #define debug(...) 23
#endif

template <class U, class V> scan_op(pair <U, V>)  { return in >> u.first >> u.second; }
template <class T> scan_op(vector <T>)  { for (size_t i = 0; i < u.size(); ++i) in >> u[i]; return in; }
template <class U, class V> print_op(pair <U, V>)  { return out << '(' << u.first << ", " << u.second << ')'; }
template <size_t i, class T> ostream & print_tuple_utils(ostream &out, const T &tup) { if constexpr(i == tuple_size<T>::value) return out << ")";  else return print_tuple_utils<i + 1, T>(out << (i ? ", " : "(") << get<i>(tup), tup); }
template <class ...U> print_op(tuple<U...>) { return print_tuple_utils<0, tuple<U...>>(out, u); }
template <class Con, class = decltype(begin(declval<Con>()))> typename enable_if <!is_same<Con, string>::value, ostream&>::type operator << (ostream &out, const Con &con) { out << '{'; for (__typeof(con.begin()) it = con.begin(); it != con.end(); ++it) out << (it == con.begin() ? "" : ", ") << *it; return out << '}'; }

// end of template

vector <int> find_split(int n, int a, int b, int c, vector <int> P, vector <int> Q) {
	int m = P.size();
	vector <vector <int>> adj(n), tree_adj(n);
	REP(i, m) {
		adj[P[i]].push_back(i);
		adj[Q[i]].push_back(i);
	}

	vector <int> low(n, n + 1), num(n), treeSize(n);
	vector <bool> used(m);
	int timeDfs = 0;
	function <void(int)> dfs = [&] (int u) {
		num[u] = ++timeDfs;
		treeSize[u] = 1;
		for (int id: adj[u]) {
			used[id] = true;
			int v = P[id] ^ Q[id] ^ u;
			if (!num[v]) {
				tree_adj[u].push_back(v);
				dfs(v);
				treeSize[u] += treeSize[v];
				low[u] = min(low[u], low[v]);
			} else low[u] = min(low[u], num[v]);
		}
	};
	dfs(0);
	vector <pair <int, int>> pt;
	pt.emplace_back(a, 1);
	pt.emplace_back(b, 2);
	pt.emplace_back(c, 3);
	sort(ALL(pt));
	vector <int> res(n);
	REP(t, 2) {
		function <bool(int)> dfs2 = [&] (int u) {
			if (treeSize[u] < pt[t].fi) return false;
			bool ok = true;
			for (int v: tree_adj[u]) if (treeSize[v] >= pt[t].fi) {
				if (dfs2(v)) return true;
				ok = false;
			}
			if (ok) {
				int cur = treeSize[u];
				for (int v: tree_adj[u]) if (low[v] < num[u] && cur - treeSize[v] >= pt[t].fi) {
					res[v] = -1;
					cur -= treeSize[v];
				}
				if (n - cur >= pt[t ^ 1].fi) {
					queue <int> q;
					q.push(u);
					--pt[t].fi;
					res[u] = pt[t].se;
					while (!q.empty()) {
						int u = q.front();
						q.pop();
						for (int v: tree_adj[u]) if (!res[v]) {
							if (!pt[t].fi) break;
							--pt[t].fi;
							res[v] = pt[t].se;
							q.push(v);
						}
					}

					while (!q.empty()) q.pop();
					u = 0;
					while (res[u] == pt[t].se) ++u;
					q.push(u);
					--pt[t ^ 1].fi;
					res[u] = pt[t ^ 1].se;
					while (!q.empty()) {
						int u = q.front();
						q.pop();
						for (int id: adj[u]) {
							int v = P[id] ^ Q[id] ^ u;
							if (res[v] > 0) continue;
							if (!pt[t ^ 1].fi) break;
							--pt[t ^ 1].fi;
							res[v] = pt[t ^ 1].se;
							q.push(v);
						}
					}

					REP(i, n) if (res[i] <= 0) res[i] = pt[2].se;
					return true;
				}
				for (int v: tree_adj[u]) res[v] = 0;
			}
			return false;
		};
		if (dfs2(0)) return res;
	}
	return res;
}

Subtask #1

7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	ok, correct split
2	Correct	0 ms	212 KB	ok, correct split
3	Correct	1 ms	212 KB	ok, correct split
4	Correct	1 ms	212 KB	ok, correct split
5	Correct	1 ms	304 KB	ok, correct split
6	Correct	1 ms	212 KB	ok, correct split
7	Correct	72 ms	25164 KB	ok, correct split
8	Correct	62 ms	21688 KB	ok, correct split
9	Correct	72 ms	22816 KB	ok, correct split
10	Correct	71 ms	32752 KB	ok, correct split
11	Correct	76 ms	26936 KB	ok, correct split

Subtask #2

11.0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	296 KB	ok, correct split
2	Correct	1 ms	212 KB	ok, correct split
3	Correct	1 ms	212 KB	ok, correct split
4	Correct	71 ms	18920 KB	ok, correct split
5	Correct	74 ms	13260 KB	ok, correct split
6	Correct	71 ms	31756 KB	ok, correct split
7	Correct	73 ms	25508 KB	ok, correct split
8	Correct	81 ms	15972 KB	ok, correct split
9	Correct	83 ms	14756 KB	ok, correct split
10	Correct	37 ms	12360 KB	ok, correct split
11	Correct	36 ms	12364 KB	ok, correct split
12	Correct	47 ms	12448 KB	ok, correct split

Subtask #3

22.0 / 22.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	ok, correct split
2	Correct	53 ms	13168 KB	ok, correct split
3	Correct	19 ms	5844 KB	ok, correct split
4	Correct	1 ms	212 KB	ok, correct split
5	Correct	61 ms	18580 KB	ok, correct split
6	Correct	59 ms	18368 KB	ok, correct split
7	Correct	60 ms	18096 KB	ok, correct split
8	Correct	64 ms	19700 KB	ok, correct split
9	Correct	60 ms	17868 KB	ok, correct split
10	Correct	16 ms	4820 KB	ok, no valid answer
11	Correct	23 ms	7080 KB	ok, no valid answer
12	Correct	42 ms	13496 KB	ok, no valid answer
13	Correct	48 ms	13996 KB	ok, no valid answer
14	Correct	36 ms	13256 KB	ok, no valid answer

Subtask #4

24.0 / 24.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	ok, correct split
2	Correct	1 ms	212 KB	ok, no valid answer
3	Correct	1 ms	300 KB	ok, correct split
4	Correct	1 ms	212 KB	ok, correct split
5	Correct	1 ms	296 KB	ok, correct split
6	Correct	1 ms	300 KB	ok, correct split
7	Correct	1 ms	212 KB	ok, correct split
8	Correct	1 ms	212 KB	ok, correct split
9	Correct	2 ms	724 KB	ok, correct split
10	Correct	2 ms	724 KB	ok, correct split
11	Correct	1 ms	300 KB	ok, correct split
12	Correct	2 ms	696 KB	ok, correct split
13	Correct	1 ms	212 KB	ok, correct split
14	Correct	1 ms	212 KB	ok, correct split
15	Correct	1 ms	212 KB	ok, correct split
16	Correct	1 ms	212 KB	ok, correct split
17	Correct	1 ms	212 KB	ok, correct split
18	Correct	0 ms	300 KB	ok, correct split
19	Correct	1 ms	340 KB	ok, correct split
20	Correct	1 ms	436 KB	ok, correct split
21	Correct	2 ms	696 KB	ok, correct split
22	Correct	1 ms	724 KB	ok, correct split
23	Correct	1 ms	724 KB	ok, correct split
24	Correct	1 ms	724 KB	ok, correct split
25	Correct	1 ms	724 KB	ok, correct split
26	Correct	2 ms	596 KB	ok, correct split
27	Correct	2 ms	692 KB	ok, correct split
28	Correct	2 ms	568 KB	ok, correct split
29	Correct	1 ms	212 KB	ok, correct split
30	Correct	2 ms	696 KB	ok, correct split
31	Correct	1 ms	340 KB	ok, correct split
32	Correct	1 ms	324 KB	ok, correct split
33	Correct	1 ms	352 KB	ok, correct split
34	Correct	2 ms	596 KB	ok, correct split
35	Correct	2 ms	572 KB	ok, correct split
36	Correct	2 ms	596 KB	ok, correct split
37	Correct	2 ms	724 KB	ok, correct split
38	Correct	2 ms	724 KB	ok, correct split
39	Correct	2 ms	724 KB	ok, correct split
40	Correct	2 ms	596 KB	ok, correct split
41	Correct	1 ms	468 KB	ok, correct split
42	Correct	1 ms	468 KB	ok, correct split
43	Correct	2 ms	724 KB	ok, correct split
44	Correct	2 ms	724 KB	ok, correct split
45	Correct	3 ms	724 KB	ok, correct split
46	Correct	1 ms	724 KB	ok, correct split
47	Correct	2 ms	728 KB	ok, no valid answer
48	Correct	2 ms	596 KB	ok, correct split
49	Correct	2 ms	724 KB	ok, correct split
50	Correct	1 ms	296 KB	ok, no valid answer
51	Correct	0 ms	212 KB	ok, no valid answer
52	Correct	1 ms	596 KB	ok, no valid answer
53	Correct	2 ms	724 KB	ok, no valid answer
54	Correct	1 ms	596 KB	ok, no valid answer
55	Correct	2 ms	560 KB	ok, no valid answer
56	Correct	1 ms	568 KB	ok, no valid answer

Subtask #5

36.0 / 36.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	ok, correct split
2	Correct	0 ms	212 KB	ok, correct split
3	Correct	1 ms	212 KB	ok, correct split
4	Correct	1 ms	212 KB	ok, correct split
5	Correct	1 ms	304 KB	ok, correct split
6	Correct	1 ms	212 KB	ok, correct split
7	Correct	72 ms	25164 KB	ok, correct split
8	Correct	62 ms	21688 KB	ok, correct split
9	Correct	72 ms	22816 KB	ok, correct split
10	Correct	71 ms	32752 KB	ok, correct split
11	Correct	76 ms	26936 KB	ok, correct split
12	Correct	1 ms	296 KB	ok, correct split
13	Correct	1 ms	212 KB	ok, correct split
14	Correct	1 ms	212 KB	ok, correct split
15	Correct	71 ms	18920 KB	ok, correct split
16	Correct	74 ms	13260 KB	ok, correct split
17	Correct	71 ms	31756 KB	ok, correct split
18	Correct	73 ms	25508 KB	ok, correct split
19	Correct	81 ms	15972 KB	ok, correct split
20	Correct	83 ms	14756 KB	ok, correct split
21	Correct	37 ms	12360 KB	ok, correct split
22	Correct	36 ms	12364 KB	ok, correct split
23	Correct	47 ms	12448 KB	ok, correct split
24	Correct	1 ms	212 KB	ok, correct split
25	Correct	53 ms	13168 KB	ok, correct split
26	Correct	19 ms	5844 KB	ok, correct split
27	Correct	1 ms	212 KB	ok, correct split
28	Correct	61 ms	18580 KB	ok, correct split
29	Correct	59 ms	18368 KB	ok, correct split
30	Correct	60 ms	18096 KB	ok, correct split
31	Correct	64 ms	19700 KB	ok, correct split
32	Correct	60 ms	17868 KB	ok, correct split
33	Correct	16 ms	4820 KB	ok, no valid answer
34	Correct	23 ms	7080 KB	ok, no valid answer
35	Correct	42 ms	13496 KB	ok, no valid answer
36	Correct	48 ms	13996 KB	ok, no valid answer
37	Correct	36 ms	13256 KB	ok, no valid answer
38	Correct	1 ms	212 KB	ok, correct split
39	Correct	1 ms	212 KB	ok, no valid answer
40	Correct	1 ms	300 KB	ok, correct split
41	Correct	1 ms	212 KB	ok, correct split
42	Correct	1 ms	296 KB	ok, correct split
43	Correct	1 ms	300 KB	ok, correct split
44	Correct	1 ms	212 KB	ok, correct split
45	Correct	1 ms	212 KB	ok, correct split
46	Correct	2 ms	724 KB	ok, correct split
47	Correct	2 ms	724 KB	ok, correct split
48	Correct	1 ms	300 KB	ok, correct split
49	Correct	2 ms	696 KB	ok, correct split
50	Correct	1 ms	212 KB	ok, correct split
51	Correct	1 ms	212 KB	ok, correct split
52	Correct	1 ms	212 KB	ok, correct split
53	Correct	1 ms	212 KB	ok, correct split
54	Correct	1 ms	212 KB	ok, correct split
55	Correct	0 ms	300 KB	ok, correct split
56	Correct	1 ms	340 KB	ok, correct split
57	Correct	1 ms	436 KB	ok, correct split
58	Correct	2 ms	696 KB	ok, correct split
59	Correct	1 ms	724 KB	ok, correct split
60	Correct	1 ms	724 KB	ok, correct split
61	Correct	1 ms	724 KB	ok, correct split
62	Correct	1 ms	724 KB	ok, correct split
63	Correct	2 ms	596 KB	ok, correct split
64	Correct	2 ms	692 KB	ok, correct split
65	Correct	2 ms	568 KB	ok, correct split
66	Correct	1 ms	212 KB	ok, correct split
67	Correct	2 ms	696 KB	ok, correct split
68	Correct	1 ms	340 KB	ok, correct split
69	Correct	1 ms	324 KB	ok, correct split
70	Correct	1 ms	352 KB	ok, correct split
71	Correct	2 ms	596 KB	ok, correct split
72	Correct	2 ms	572 KB	ok, correct split
73	Correct	2 ms	596 KB	ok, correct split
74	Correct	2 ms	724 KB	ok, correct split
75	Correct	2 ms	724 KB	ok, correct split
76	Correct	2 ms	724 KB	ok, correct split
77	Correct	2 ms	596 KB	ok, correct split
78	Correct	1 ms	468 KB	ok, correct split
79	Correct	1 ms	468 KB	ok, correct split
80	Correct	2 ms	724 KB	ok, correct split
81	Correct	2 ms	724 KB	ok, correct split
82	Correct	3 ms	724 KB	ok, correct split
83	Correct	1 ms	724 KB	ok, correct split
84	Correct	2 ms	728 KB	ok, no valid answer
85	Correct	2 ms	596 KB	ok, correct split
86	Correct	2 ms	724 KB	ok, correct split
87	Correct	1 ms	296 KB	ok, no valid answer
88	Correct	0 ms	212 KB	ok, no valid answer
89	Correct	1 ms	596 KB	ok, no valid answer
90	Correct	2 ms	724 KB	ok, no valid answer
91	Correct	1 ms	596 KB	ok, no valid answer
92	Correct	2 ms	560 KB	ok, no valid answer
93	Correct	1 ms	568 KB	ok, no valid answer
94	Correct	68 ms	19824 KB	ok, correct split
95	Correct	104 ms	26976 KB	ok, correct split
96	Correct	89 ms	24816 KB	ok, correct split
97	Correct	19 ms	5776 KB	ok, correct split
98	Correct	21 ms	6032 KB	ok, correct split
99	Correct	31 ms	8328 KB	ok, correct split
100	Correct	108 ms	18500 KB	ok, correct split
101	Correct	75 ms	17244 KB	ok, correct split
102	Correct	67 ms	16756 KB	ok, correct split
103	Correct	68 ms	16380 KB	ok, correct split
104	Correct	58 ms	16536 KB	ok, correct split
105	Correct	30 ms	8788 KB	ok, correct split
106	Correct	62 ms	16344 KB	ok, correct split
107	Correct	52 ms	14156 KB	ok, correct split
108	Correct	79 ms	14112 KB	ok, correct split
109	Correct	76 ms	17864 KB	ok, correct split
110	Correct	79 ms	18724 KB	ok, correct split
111	Correct	79 ms	18864 KB	ok, correct split
112	Correct	84 ms	17584 KB	ok, correct split
113	Correct	75 ms	17480 KB	ok, correct split
114	Correct	8 ms	2616 KB	ok, correct split
115	Correct	7 ms	2232 KB	ok, correct split
116	Correct	86 ms	18612 KB	ok, correct split
117	Correct	82 ms	18520 KB	ok, correct split
118	Correct	55 ms	15652 KB	ok, correct split
119	Correct	53 ms	15556 KB	ok, correct split
120	Correct	61 ms	20456 KB	ok, correct split
121	Correct	49 ms	14072 KB	ok, no valid answer
122	Correct	58 ms	14008 KB	ok, no valid answer
123	Correct	76 ms	18756 KB	ok, no valid answer
124	Correct	79 ms	18492 KB	ok, no valid answer
125	Correct	52 ms	14916 KB	ok, no valid answer
126	Correct	40 ms	11980 KB	ok, no valid answer
127	Correct	55 ms	15928 KB	ok, no valid answer