oj.uz

Submission #564892

# Submission time Handle Problem Language Result Execution time Memory
564892 2022-05-19T23:06:24 Z Bungmint Bitaro’s Party (JOI18_bitaro) C++17
100 / 100
 1252 ms 422620 KB 
// Copyright © 2022 Youngmin Park. All rights reserved.
#pragma GCC optimize("O3")
//#pragma GCC target("avx2")
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using vi = vector<int>;
using pii = pair<int, int>;
using vpi = vector<pii>;
using pll = pair<ll, ll>;
using vl = vector<ll>;
using vpl = vector<pll>;
using ld = long double;
template <typename T, size_t SZ>
using ar = array<T, SZ>;
template <typename T>
using pqg = priority_queue<T, vector<T>, greater<T>>;

#define all(v) (v).begin(), (v).end()
#define pb push_back
#define sz(x) (int)(x).size()
#define fi first
#define se second
#define lb lower_bound
#define ub upper_bound

constexpr int INF = 1e9;
constexpr ll LINF = 1e18;
const ld PI = acos((ld)-1.0);
constexpr int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
template <typename T>
constexpr bool ckmin(T &a, const T &b) { return b < a ? a = b, 1 : 0; }
template <typename T>
constexpr bool ckmax(T &a, const T &b) { return b > a ? a = b, 1 : 0; }

template <typename A, typename B>
ostream &operator<<(ostream &os, const pair<A, B> &p)
{
	return os << '(' << p.first << ", " << p.second << ')';
}
template <typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type>
ostream &operator<<(ostream &os, const T_container &v)
{
	os << '{';
	string sep;
	for (const T &x : v)
		os << sep << x, sep = ", ";
	return os << '}';
}
template <typename T>
ostream &operator<<(ostream &os, const deque<T> &v) {
	os << vector<T>(all(v));
	return os;
}
template <typename T, typename S, typename C>
ostream &operator<<(ostream &os, priority_queue<T, S, C> pq) {
	vector<T> v;
	while (sz(pq)) {
		v.pb(pq.top());
		pq.pop();
	}
	os << v;
	return os;
}
void dbg_out()
{
	cerr << "\033[0m" << endl;
}
template <typename Head, typename... Tail>
void dbg_out(Head H, Tail... T)
{
	cerr << ' ' << H;
	dbg_out(T...);
}
#ifdef LOCAL
#define dbg(...) cerr << "\033[1;35m(" << #__VA_ARGS__ << "):\033[33m", dbg_out(__VA_ARGS__)
#else
#define dbg(...) 42
#endif

inline namespace RecursiveLambda
{
	template <typename Fun>
	struct y_combinator_result
	{
		Fun fun_;
		template <typename T>
		explicit y_combinator_result(T &&fun) : fun_(forward<T>(fun)) {}
		template <typename... Args>
		decltype(auto) operator()(Args &&...args)
		{
			return fun_(ref(*this), forward<Args>(args)...);
		}
	};
	template <typename Fun>
	decltype(auto) y_combinator(Fun &&fun)
	{
		return y_combinator_result<decay_t<Fun>>(forward<Fun>(fun));
	}
};

inline namespace Range {
	class ForwardRange {
		int src, dst;

	  public:
	  	explicit constexpr ForwardRange(const int l, const int r) : src(l), dst(r) {}
		explicit constexpr ForwardRange(const int n) : src(0), dst(n) {}
		constexpr ForwardRange begin() const { return *this; }
		constexpr monostate end() const { return {}; }
		constexpr bool operator!=(monostate) const { return src < dst; }
		constexpr void operator++() const {}
		constexpr int operator*() { return src++; }
	};
	class BackwardRange {
		int src, dst;

	  public:
	  	explicit constexpr BackwardRange(const int l, const int r) : src(r), dst(l) {}
		explicit constexpr BackwardRange(const int n) : src(n), dst(0) {}
		constexpr BackwardRange begin() const { return *this; }
		constexpr monostate end() const { return {}; }
		constexpr bool operator!=(monostate) const { return src > dst; }
		constexpr void operator++() const {}
		constexpr int operator*() { return --src; }
	};
	using rep = ForwardRange;
	using per = BackwardRange;
};

constexpr int N = 1e5 + 10;
constexpr int SQ = 320;
int n, m, q;
vi adj[N], radj[N], queries[N];
bitset<N> busy, used;
int t[N], DP[N];
vpi dp[N];

void solve()
{
	cin >> n >> m >> q;
	for (int i : rep(m)) {
		int u, v;
		cin >> u >> v, u--, v--;
		adj[u].pb(v), radj[v].pb(u);
	}
	for (int i : rep(n)) {
		dp[i] = {{0, i}};
		for (int j : radj[i]) {
			vpi res;
			int sa = sz(dp[i]), sb = sz(dp[j]);
			int a = 0, b = 0;
			while (sz(res) < SQ && (a < sa || b < sb)) {
				if (b == sb || (a != sa && dp[i][a].fi >= dp[j][b].fi + 1)) {
					if (used[dp[i][a].se]) a++;
					else{
						res.pb(dp[i][a]);
						used[dp[i][a].se] = 1;
						a++;
					}
				}else{
					if (used[dp[j][b].se]) b++;
					else{
						res.pb({dp[j][b].fi + 1, dp[j][b].se});
						used[dp[j][b].se] = 1;
						b++;
					}
				}
			}
			for (auto [d, v] : res) used[v] = 0;
			swap(res, dp[i]);
		}
		dbg(dp[i]);
	}
	auto naiveDP = [&](int t, vi& C) -> int {
		for (int i : rep(n)) DP[i] = 0;
		for (int i : C) DP[i] = -1;
		for (int i : rep(t + 1)) {
			for (int j : radj[i]) {
				if (DP[j] >= 0) ckmax(DP[i], DP[j] + 1);
			}
		}
		return DP[t];
	};
	for (int i : rep(q)) {
		cin >> t[i];
		t[i]--;
		int x;
		cin >> x;
		queries[i].resize(x);
		for (auto &e : queries[i]) cin >> e, e--, busy[e] = 1;
		if (x >= SQ) {
			cout << naiveDP(t[i], queries[i]) << '\n';
		}else{
			int ans = -1;
			for (auto &[d, v] : dp[t[i]]) {
				if (!busy[v]) ckmax(ans, d);
			}
			cout << ans << '\n';
		}
		for (auto &e : queries[i]) busy[e] = 0;
	}
}

int main()
{
	cin.tie(0)->sync_with_stdio(0);
	cin.exceptions(cin.failbit);
	int testcase = 1;
	// cin >> testcase;
	while (testcase--)
	{
		solve();
	}
#ifdef LOCAL
	cerr << "Time elapsed: " << 1.0 * (double)clock() / CLOCKS_PER_SEC << " s.\n";
#endif
}

Compilation message

bitaro.cpp: In function 'void solve()':
bitaro.cpp:144:11: warning: unused variable 'i' [-Wunused-variable]
  144 |  for (int i : rep(m)) {
      |           ^
bitaro.cpp:80:18: warning: statement has no effect [-Wunused-value]
   80 | #define dbg(...) 42
      |                  ^~
bitaro.cpp:175:3: note: in expansion of macro 'dbg'
  175 |   dbg(dp[i]);
      |   ^~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9684 KB Output is correct
2 Correct 6 ms 9684 KB Output is correct
3 Correct 6 ms 9684 KB Output is correct
4 Correct 7 ms 9720 KB Output is correct
5 Correct 9 ms 10152 KB Output is correct
6 Correct 9 ms 10248 KB Output is correct
7 Correct 9 ms 10196 KB Output is correct
8 Correct 17 ms 13060 KB Output is correct
9 Correct 15 ms 13060 KB Output is correct
10 Correct 15 ms 13124 KB Output is correct
11 Correct 15 ms 12760 KB Output is correct
12 Correct 10 ms 11080 KB Output is correct
13 Correct 15 ms 12452 KB Output is correct
14 Correct 14 ms 11720 KB Output is correct
15 Correct 11 ms 10692 KB Output is correct
16 Correct 14 ms 11732 KB Output is correct
17 Correct 13 ms 11952 KB Output is correct
18 Correct 11 ms 10964 KB Output is correct
19 Correct 13 ms 11920 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9684 KB Output is correct
2 Correct 6 ms 9684 KB Output is correct
3 Correct 6 ms 9684 KB Output is correct
4 Correct 7 ms 9720 KB Output is correct
5 Correct 9 ms 10152 KB Output is correct
6 Correct 9 ms 10248 KB Output is correct
7 Correct 9 ms 10196 KB Output is correct
8 Correct 17 ms 13060 KB Output is correct
9 Correct 15 ms 13060 KB Output is correct
10 Correct 15 ms 13124 KB Output is correct
11 Correct 15 ms 12760 KB Output is correct
12 Correct 10 ms 11080 KB Output is correct
13 Correct 15 ms 12452 KB Output is correct
14 Correct 14 ms 11720 KB Output is correct
15 Correct 11 ms 10692 KB Output is correct
16 Correct 14 ms 11732 KB Output is correct
17 Correct 13 ms 11952 KB Output is correct
18 Correct 11 ms 10964 KB Output is correct
19 Correct 13 ms 11920 KB Output is correct
20 Correct 926 ms 15568 KB Output is correct
21 Correct 886 ms 15572 KB Output is correct
22 Correct 924 ms 15608 KB Output is correct
23 Correct 985 ms 15716 KB Output is correct
24 Correct 912 ms 259620 KB Output is correct
25 Correct 969 ms 273432 KB Output is correct
26 Correct 930 ms 272536 KB Output is correct
27 Correct 1192 ms 420916 KB Output is correct
28 Correct 1193 ms 420828 KB Output is correct
29 Correct 1221 ms 420772 KB Output is correct
30 Correct 1202 ms 419660 KB Output is correct
31 Correct 1205 ms 405252 KB Output is correct
32 Correct 1230 ms 419576 KB Output is correct
33 Correct 906 ms 262464 KB Output is correct
34 Correct 802 ms 216284 KB Output is correct
35 Correct 883 ms 260736 KB Output is correct
36 Correct 1040 ms 341452 KB Output is correct
37 Correct 946 ms 309740 KB Output is correct
38 Correct 1018 ms 342588 KB Output is correct

Subtask #3
86.0 / 86.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9684 KB Output is correct
2 Correct 6 ms 9684 KB Output is correct
3 Correct 6 ms 9684 KB Output is correct
4 Correct 7 ms 9720 KB Output is correct
5 Correct 9 ms 10152 KB Output is correct
6 Correct 9 ms 10248 KB Output is correct
7 Correct 9 ms 10196 KB Output is correct
8 Correct 17 ms 13060 KB Output is correct
9 Correct 15 ms 13060 KB Output is correct
10 Correct 15 ms 13124 KB Output is correct
11 Correct 15 ms 12760 KB Output is correct
12 Correct 10 ms 11080 KB Output is correct
13 Correct 15 ms 12452 KB Output is correct
14 Correct 14 ms 11720 KB Output is correct
15 Correct 11 ms 10692 KB Output is correct
16 Correct 14 ms 11732 KB Output is correct
17 Correct 13 ms 11952 KB Output is correct
18 Correct 11 ms 10964 KB Output is correct
19 Correct 13 ms 11920 KB Output is correct
20 Correct 926 ms 15568 KB Output is correct
21 Correct 886 ms 15572 KB Output is correct
22 Correct 924 ms 15608 KB Output is correct
23 Correct 985 ms 15716 KB Output is correct
24 Correct 912 ms 259620 KB Output is correct
25 Correct 969 ms 273432 KB Output is correct
26 Correct 930 ms 272536 KB Output is correct
27 Correct 1192 ms 420916 KB Output is correct
28 Correct 1193 ms 420828 KB Output is correct
29 Correct 1221 ms 420772 KB Output is correct
30 Correct 1202 ms 419660 KB Output is correct
31 Correct 1205 ms 405252 KB Output is correct
32 Correct 1230 ms 419576 KB Output is correct
33 Correct 906 ms 262464 KB Output is correct
34 Correct 802 ms 216284 KB Output is correct
35 Correct 883 ms 260736 KB Output is correct
36 Correct 1040 ms 341452 KB Output is correct
37 Correct 946 ms 309740 KB Output is correct
38 Correct 1018 ms 342588 KB Output is correct
39 Correct 1056 ms 264704 KB Output is correct
40 Correct 941 ms 266872 KB Output is correct
41 Correct 926 ms 269604 KB Output is correct
42 Correct 1048 ms 268308 KB Output is correct
43 Correct 961 ms 267564 KB Output is correct
44 Correct 978 ms 20068 KB Output is correct
45 Correct 927 ms 17828 KB Output is correct
46 Correct 907 ms 17504 KB Output is correct
47 Correct 931 ms 17360 KB Output is correct
48 Correct 935 ms 17072 KB Output is correct
49 Correct 1219 ms 422620 KB Output is correct
50 Correct 1152 ms 420476 KB Output is correct
51 Correct 911 ms 19916 KB Output is correct
52 Correct 877 ms 17608 KB Output is correct
53 Correct 1113 ms 341964 KB Output is correct
54 Correct 1041 ms 311836 KB Output is correct
55 Correct 1018 ms 340176 KB Output is correct
56 Correct 977 ms 310580 KB Output is correct
57 Correct 1002 ms 19996 KB Output is correct
58 Correct 1051 ms 19892 KB Output is correct
59 Correct 925 ms 17588 KB Output is correct
60 Correct 946 ms 17524 KB Output is correct
61 Correct 1225 ms 420436 KB Output is correct
62 Correct 1120 ms 341412 KB Output is correct
63 Correct 1085 ms 309012 KB Output is correct
64 Correct 1252 ms 420300 KB Output is correct
65 Correct 1237 ms 339856 KB Output is correct
66 Correct 1232 ms 310544 KB Output is correct
67 Correct 1114 ms 419900 KB Output is correct
68 Correct 1029 ms 340984 KB Output is correct
69 Correct 965 ms 306400 KB Output is correct
70 Correct 1131 ms 420184 KB Output is correct
71 Correct 1022 ms 341476 KB Output is correct
72 Correct 992 ms 309724 KB Output is correct
73 Correct 1126 ms 420100 KB Output is correct
74 Correct 1038 ms 341368 KB Output is correct
75 Correct 1025 ms 309792 KB Output is correct
76 Correct 1240 ms 421760 KB Output is correct
77 Correct 1104 ms 419496 KB Output is correct
78 Correct 1117 ms 419908 KB Output is correct
79 Correct 920 ms 18888 KB Output is correct
80 Correct 869 ms 16800 KB Output is correct
81 Correct 882 ms 16680 KB Output is correct
82 Correct 1237 ms 420456 KB Output is correct
83 Correct 1227 ms 405964 KB Output is correct
84 Correct 1128 ms 418060 KB Output is correct
85 Correct 1135 ms 403400 KB Output is correct
86 Correct 1148 ms 418444 KB Output is correct
87 Correct 1143 ms 404788 KB Output is correct
88 Correct 1063 ms 18800 KB Output is correct
89 Correct 1018 ms 18696 KB Output is correct
90 Correct 980 ms 16452 KB Output is correct
91 Correct 940 ms 16640 KB Output is correct
92 Correct 933 ms 16392 KB Output is correct
93 Correct 905 ms 16392 KB Output is correct
94 Correct 988 ms 263436 KB Output is correct
95 Correct 866 ms 215748 KB Output is correct
96 Correct 913 ms 259764 KB Output is correct
97 Correct 807 ms 217940 KB Output is correct
98 Correct 888 ms 260996 KB Output is correct
99 Correct 792 ms 217496 KB Output is correct
100 Correct 1044 ms 18560 KB Output is correct
101 Correct 1012 ms 18648 KB Output is correct
102 Correct 963 ms 16456 KB Output is correct
103 Correct 946 ms 16528 KB Output is correct
104 Correct 954 ms 16288 KB Output is correct
105 Correct 933 ms 16376 KB Output is correct
106 Correct 1062 ms 341200 KB Output is correct
107 Correct 1012 ms 310860 KB Output is correct
108 Correct 982 ms 341124 KB Output is correct
109 Correct 915 ms 308404 KB Output is correct
110 Correct 986 ms 341612 KB Output is correct
111 Correct 939 ms 309760 KB Output is correct
112 Correct 937 ms 18772 KB Output is correct
113 Correct 989 ms 18648 KB Output is correct
114 Correct 870 ms 16440 KB Output is correct
115 Correct 912 ms 16512 KB Output is correct
116 Correct 894 ms 16444 KB Output is correct
117 Correct 890 ms 16332 KB Output is correct
118 Correct 1072 ms 418888 KB Output is correct
119 Correct 983 ms 340640 KB Output is correct
120 Correct 929 ms 307796 KB Output is correct
121 Correct 1079 ms 418976 KB Output is correct
122 Correct 1000 ms 339420 KB Output is correct
123 Correct 924 ms 308076 KB Output is correct
124 Correct 1082 ms 418772 KB Output is correct
125 Correct 985 ms 340684 KB Output is correct
126 Correct 917 ms 306824 KB Output is correct