fork download 
  1. // base off ecnerwala's solution...
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4.  
  5. template <int MOD_> struct modnum {
  6. 	static constexpr int MOD = MOD_;
  7. 	static_assert(MOD_ > 0, "MOD must be positive");
  8.  
  9. private:
  10. 	using ll = long long;
  11.  
  12. 	int v;
  13.  
  14. 	static int minv(int a, int m) {
  15. 		a %= m;
  16. 		assert(a);
  17. 		return a == 1 ? 1 : int(m - ll(minv(m, a)) * ll(m) / a);
  18. 	}
  19.  
  20. public:
  21.  
  22. 	modnum() : v(0) {}
  23. 	modnum(ll v_) : v(int(v_ % MOD)) { if (v < 0) v += MOD; }
  24. 	explicit operator int() const { return v; }
  25. 	friend std::ostream& operator << (std::ostream& out, const modnum& n) { return out << int(n); }
  26. 	friend std::istream& operator >> (std::istream& in, modnum& n) { ll v_; in >> v_; n = modnum(v_); return in; }
  27.  
  28. 	friend bool operator == (const modnum& a, const modnum& b) { return a.v == b.v; }
  29. 	friend bool operator != (const modnum& a, const modnum& b) { return a.v != b.v; }
  30.  
  31. 	modnum inv() const {
  32. 		modnum res;
  33. 		res.v = minv(v, MOD);
  34. 		return res;
  35. 	}
  36. 	friend modnum inv(const modnum& m) { return m.inv(); }
  37. 	modnum neg() const {
  38. 		modnum res;
  39. 		res.v = v ? MOD-v : 0;
  40. 		return res;
  41. 	}
  42. 	friend modnum neg(const modnum& m) { return m.neg(); }
  43.  
  44. 	modnum operator- () const {
  45. 		return neg();
  46. 	}
  47. 	modnum operator+ () const {
  48. 		return modnum(*this);
  49. 	}
  50.  
  51. 	modnum& operator ++ () {
  52. 		v ++;
  53. 		if (v == MOD) v = 0;
  54. 		return *this;
  55. 	}
  56. 	modnum& operator -- () {
  57. 		if (v == 0) v = MOD;
  58. 		v --;
  59. 		return *this;
  60. 	}
  61. 	modnum& operator += (const modnum& o) {
  62. 		v += o.v;
  63. 		if (v >= MOD) v -= MOD;
  64. 		return *this;
  65. 	}
  66. 	modnum& operator -= (const modnum& o) {
  67. 		v -= o.v;
  68. 		if (v < 0) v += MOD;
  69. 		return *this;
  70. 	}
  71. 	modnum& operator *= (const modnum& o) {
  72. 		v = int(ll(v) * ll(o.v) % MOD);
  73. 		return *this;
  74. 	}
  75. 	modnum& operator /= (const modnum& o) {
  76. 		return *this *= o.inv();
  77. 	}
  78.  
  79. 	friend modnum operator ++ (modnum& a, int) { modnum r = a; ++a; return r; }
  80. 	friend modnum operator -- (modnum& a, int) { modnum r = a; --a; return r; }
  81. 	friend modnum operator + (const modnum& a, const modnum& b) { return modnum(a) += b; }
  82. 	friend modnum operator - (const modnum& a, const modnum& b) { return modnum(a) -= b; }
  83. 	friend modnum operator * (const modnum& a, const modnum& b) { return modnum(a) *= b; }
  84. 	friend modnum operator / (const modnum& a, const modnum& b) { return modnum(a) /= b; }
  85. };
  86.  
  87. template <typename T> T pow(T a, long long b) {
  88. 	assert(b >= 0);
  89. 	T r = 1; while (b) { if (b & 1) r *= a; b >>= 1; a *= a; } return r;
  90. }
  91.  
  92. using num = modnum<int(1e9) + 7>;
  93.  
  94. using ll = long long;
  95.  
  96. struct DSU {
  97. 	vector<int> par;
  98. 	DSU() {}
  99. 	DSU(int n) : par(n, -1) {}
  100. 	int getpar(int a) {
  101. 		return par[a] < 0 ? a : (par[a] = getpar(par[a]));
  102. 	}
  103. 	bool merge(int a, int b) {
  104. 		a = getpar(a);
  105. 		b = getpar(b);
  106. 		if (a == b) return false;
  107. 		if (-par[a] < -par[b]) swap(a, b);
  108. 		par[a] += par[b];
  109. 		par[b] = a;
  110. 		return true;
  111. 	}
  112. };
  113.  
  114. struct node {
  115. 	ll a, b, d;
  116. 	int c, e;
  117.  
  118. 	bool is_root;
  119. 	int root;
  120. 	int depth;
  121. 	int idx;
  122.  
  123. 	vector<int> ch;
  124.  
  125. 	int cyc_len;
  126. 	ll cyc_offset;
  127. 	unordered_map<ll, map<ll, int>> cyc_ends;
  128. };
  129.  
  130. vector<node> nodes;
  131.  
  132. int main() {
  133. 	ios::sync_with_stdio(0), cin.tie(0);
  134.  
  135. 	int n;
  136. 	ll x0;
  137. 	cin >> n >> x0;
  138. 	nodes.resize(n+1);
  139. 	for (int i = 0; i < n; i++) {
  140. 		cin >> nodes[i].a >> nodes[i].b >> nodes[i].c >> nodes[i].d >> nodes[i].e;
  141. 		nodes[i].c--; nodes[i].e--;
  142. 		nodes[i].b += nodes[i].a;
  143. 	}
  144. 	nodes[n].a = nodes[n].b = nodes[n].d = 0;
  145. 	nodes[n].c = nodes[n].e = n;
  146.  
  147. 	vector<int> roots;
  148. 	{
  149. 		DSU dsu(n+1);
  150. 		for (int i = 0; i <= n; i++) {
  151. 			if (dsu.merge(i, nodes[i].e)) {
  152. 				nodes[nodes[i].e].ch.push_back(i);
  153. 				nodes[i].is_root = false;
  154. 			} else {
  155. 				roots.push_back(i);
  156. 				nodes[i].is_root = true;
  157. 			}
  158. 		}
  159. 		assert(roots.back() == n);
  160. 	}
  161.  
  162. 	unordered_map<ll, map<int, int>> tree_ends;
  163. 	{
  164. 		int cur_idx = 0;
  165. 		for (int root : roots) {
  166. 			ll cyc_offset = nodes[root].d;
  167. 			nodes[root].d = 0;
  168. 			nodes[root].depth = 0;
  169. 			function<void(int)> dfs = [&](int v) {
  170. 				nodes[v].root = root;
  171. 				nodes[v].idx = cur_idx;
  172. 				nodes[v].a += nodes[v].d;
  173. 				if (!tree_ends.count(nodes[v].a)) {
  174. 					tree_ends[nodes[v].a][0] = -1;
  175. 				}
  176. 				int old_val = tree_ends[nodes[v].a].rbegin()->second;
  177. 				assert(cur_idx >= tree_ends[nodes[v].a].rbegin()->first);
  178. 				tree_ends[nodes[v].a][cur_idx] = v;
  179.  
  180. 				cur_idx++;
  181. 				for (int w : nodes[v].ch) {
  182. 					nodes[w].d += nodes[v].d;
  183. 					nodes[w].depth = nodes[v].depth + 1;
  184. 					dfs(w);
  185. 				}
  186. 				assert(cur_idx >= tree_ends[nodes[v].a].rbegin()->first);
  187. 				tree_ends[nodes[v].a][cur_idx] = old_val; // 退出
  188. 			};
  189. 			dfs(root);
  190. 			cyc_offset += nodes[nodes[root].e].d;
  191. 			unordered_map<ll, map<ll, int>> cyc_ends;
  192. 			for (int cur = nodes[root].e; true; cur = nodes[cur].e) {
  193. 				ll val = nodes[cur].a;
  194. 				ll mod_val;
  195. 				if (cyc_offset == 0) {
  196. 					mod_val = val;
  197. 				} else if (cyc_offset > 0) {
  198. 					mod_val = (val % cyc_offset + cyc_offset) % cyc_offset;
  199. 				} else {
  200. 					val = -val;
  201. 					mod_val = (val % -cyc_offset + -cyc_offset) % -cyc_offset;
  202. 				}
  203. 				if (!cyc_ends[mod_val].count(val)) {
  204. 					cyc_ends[mod_val][val] = cur;
  205. 				}
  206. 				if (cur == root) break;
  207. 			}
  208. 			nodes[root].cyc_len = nodes[nodes[root].e].depth + 1;
  209. 			nodes[root].cyc_offset = cyc_offset;
  210. 			nodes[root].cyc_ends = cyc_ends;
  211. 		}
  212. 		assert(cur_idx == n+1);
  213. 	}
  214.  
  215. 	int cur = 0;
  216. 	ll x = x0 + nodes[cur].d;
  217. 	num ans = 0;
  218. 	vector<bool> vis(n);
  219. 	while (cur != n) {
  220. 		if (x == nodes[cur].a) {
  221. 			if (vis[cur]) {
  222. 				cout << -1 << '\n';
  223. 				exit(0);
  224. 			}
  225. 			vis[cur] = true;
  226. 			x = nodes[cur].b;
  227. 			cur = nodes[cur].c;
  228. 			x += nodes[cur].d;
  229. 			ans++;
  230. 		} else if (nodes[cur].is_root) {
  231. 			// x + (mod - D_tgt) + k * mod = A - D_tgt
  232. 			// x + (k+1) * mod = A
  233. 			// greater
  234. 			int cyc_len = nodes[cur].cyc_len;
  235. 			ll cyc_offset = nodes[cur].cyc_offset;
  236. 			auto& cyc_ends = nodes[cur].cyc_ends;
  237. 			if (cyc_offset == 0) {
  238. 				if (!cyc_ends.count(x)) {
  239. 					// we're screwed
  240. 					cout << -1 << '\n';
  241. 					exit(0);
  242. 				}
  243. 				int nxt = cyc_ends[x][x];
  244. 				ans += cyc_len - nodes[nxt].depth;
  245. 				cur = nxt;
  246. 			} else {
  247. 				ll mod = cyc_offset;
  248. 				if (mod < 0) {
  249. 					x = -x;
  250. 					mod = -mod;
  251. 				}
  252. 				ll mod_x = (x % mod + mod) % mod;
  253. 				if (!cyc_ends.count(mod_x)) {
  254. 					cout << -1 << '\n';
  255. 					exit(0);
  256. 				}
  257. 				auto& mod_vals = cyc_ends[mod_x];
  258. 				if (!cyc_ends.count(mod_x)) {
  259. 					cout << -1 << '\n';
  260. 					exit(0);
  261. 				}
  262. 				auto it = mod_vals.upper_bound(x);
  263. 				if (it == mod_vals.end()) {
  264. 					cout << -1 << '\n';
  265. 					exit(0);
  266. 				}
  267. 				int nxt = it->second;
  268. 				ans += num((cyc_len) * (it->first - x) / mod) - nodes[nxt].depth;
  269. 				cur = nxt;
  270. 			}
  271. 			x = nodes[cur].a;
  272. 		} else {
  273. 			int nxt = nodes[cur].root;
  274. 			if (tree_ends.count(x)) {
  275. 				auto it = tree_ends[x].upper_bound(nodes[cur].idx);
  276. 				assert(it != tree_ends[x].begin());
  277. 				--it;
  278. 				if (it->second != -1) {
  279. 					nxt = it->second;
  280. 					assert(x == nodes[nxt].a);
  281. 					assert(nodes[nxt].root = nodes[cur].root);
  282. 				}
  283. 			}
  284. 			ans += nodes[cur].depth - nodes[nxt].depth;
  285. 			cur = nxt;
  286. 		}
  287. 	}
  288. 	cout << ans << '\n';
  289. }
  290.  
Success #stdin #stdout 0s 4524KB
comments (?)
stdin 
2 0
5 1 2 1 1
10 1 3 2 2
stdout 
9
https://ideone.com/eWbCuk
language:
C++14 (gcc 8.3)
created:
5 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!