Submission #538715
Source Code Expand
#include <iostream> #include <string> #include <vector> #include <algorithm> #include <cstdio> #include <map> #include <cassert> #include <set> #include <cstring> using namespace std; typedef long long ll; typedef pair<int, int> P; /** * Link-Cut Tree * * 機能としては、link、cut、evert、parent, rootを実装済み * 辺に値を持たせたい場合は頂点倍加 */ struct LCNode { typedef LCNode* NP; typedef int D; struct Node { int d, mi; } n; LCNode() : l(nullptr), r(nullptr), sz(0), rev(false) { n.d = n.mi = 1e9+1; } LCNode(int d) : p(nullptr), l(last), r(last), sz(1), rev(false) { n.d = n.mi = d; } NP update() { assert(this != last); sz = 1+l->sz+r->sz; n.mi = n.d; if (l->sz) { n.mi = min(n.mi, l->n.mi); } if (r->sz) { n.mi = min(n.mi, r->n.mi); } return this; } void push() { int lsz = l->sz, rsz = r->sz; if (rev) { if (lsz) { l->revdata(); } if (rsz) { r->revdata(); } rev = false; } } void revdata() { assert(this != last); swap(l, r); rev ^= true; } NP search(int x) { push(); if (r->n.mi <= x) { return r->search(x); } if (n.d <= x) { expose(); return this; } if (l->n.mi <= x) { return l->search(x); } expose(); return nullptr; } //ここから static LCNode last_d; static NP last; NP p, l, r; int sz; bool rev; inline int pos() { if (p) { if (p->l == this) return -1; if (p->r == this) return 1; } return 0; } void rot() { NP qq = p->p; int pps = p->pos(); if (p->l == this) { p->l = r; r->p = p; r = p; p->p = this; } else { p->r = l; l->p = p; l = p; p->p = this; } p->update(); update(); p = qq; if (!pps) return; if (pps == -1) { qq->l = this; } else { qq->r = this; } qq->update(); } void splay() { assert(this != last); supush(); int ps; while ((ps = pos())) { int pps = p->pos(); if (!pps) { rot(); } else if (ps == pps) { p->rot(); rot(); } else { rot(); rot(); } } } void expose() { assert(this != last); NP u = this, ur = last; do { u->splay(); u->r = ur; u->update(); ur = u; } while ((u = u->p)); splay(); } /** * splayする前に一括でその頂点のパス木の根までをpushする * 唯一stack overflowしうる関数なので注意すること */ void supush() { if (pos()) { p->supush(); } push(); } //ここまでは絶対必要 void link(NP r) { assert(this != r); expose(); r->expose(); assert(l == last); p = r; } void cut() { expose(); l->p = NULL; l = last; update(); } NP root() { expose(); NP u = this; while (u->l != last) { u = u->l; u->push(); } u->expose(); //これを忘れると計算量がオワコンする return u; } NP parent() { expose(); NP u = this->l; if (u == last) return nullptr; u->push(); while (u->r != last) { u = u->r; u->push(); } u->expose(); return u; } void evert() { expose(); revdata(); } NP lca(NP n) { n->expose(); expose(); NP t = n; while (n->p != nullptr) { if (!n->pos()) t = n->p; n = n->p; } return (this == n) ? t : nullptr; } }; LCNode LCNode::last_d = LCNode(); LCNode::NP LCNode::last = &last_d; const int MN = 100100; LCNode tr[MN]; int main() { int n, q; cin >> n >> q; for (int i = 0; i < n; i++) { int a; cin >> a; tr[i] = LCNode(a); } for (int i = 0; i < n-1; i++) { int b, c; cin >> b >> c; b--; c--; tr[b].evert(); tr[b].link(tr + c); } for (int i = 0; i < q; i++) { int x, v, w; cin >> x >> v >> w; v--; w--; tr[w].evert(); tr[v].expose(); LCNode* t = tr+v; while (true) { t = t->search(x); if (t == nullptr) break; // printf("se %d \n", t->n.d); x %= t->n.d; } cout << x << endl; } return 0; }
Submission Info
Submission Time | |
---|---|
Task | J - MODクエリ |
User | yosupo |
Language | C++11 (GCC 4.9.2) |
Score | 400 |
Code Size | 5256 Byte |
Status | AC |
Exec Time | 1468 ms |
Memory | 5420 KB |
Judge Result
Set Name | Small | All | ||||
---|---|---|---|---|---|---|
Score / Max Score | 30 / 30 | 370 / 370 | ||||
Status |
|
|
Set Name | Test Cases |
---|---|
Small | 00_sample_path_01.txt, 15_path_00.txt, 15_path_01.txt, 15_path_02.txt, 15_path_03.txt, 15_path_04.txt, 16_path_05.txt, 16_path_06.txt, 16_path_07.txt, 16_path_08.txt, 16_path_09.txt, 17_path_10.txt, 17_path_11.txt, 17_path_12.txt, 17_path_13.txt, 17_path_14.txt |
All | 00_sample_path_01.txt, 15_path_00.txt, 15_path_01.txt, 15_path_02.txt, 15_path_03.txt, 15_path_04.txt, 16_path_05.txt, 16_path_06.txt, 16_path_07.txt, 16_path_08.txt, 16_path_09.txt, 17_path_10.txt, 17_path_11.txt, 17_path_12.txt, 17_path_13.txt, 17_path_14.txt, 20_random_15.txt, 20_random_16.txt, 20_random_17.txt, 21_random_18.txt, 21_random_19.txt, 21_random_20.txt, 30_random_21.txt, 30_random_22.txt, 30_random_23.txt, 40_random_24.txt, 40_random_25.txt, 40_random_26.txt, 49_sample_02.txt, 61_test_27.txt, 61_test_28.txt, 61_test_29.txt, 63_star_30.txt, 63_star_31.txt, 63_star_32.txt, 64_three_33.txt, 64_three_34.txt, 64_three_35.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
00_sample_path_01.txt | AC | 49 ms | 4880 KB |
15_path_00.txt | AC | 48 ms | 4892 KB |
15_path_01.txt | AC | 43 ms | 4828 KB |
15_path_02.txt | AC | 36 ms | 4776 KB |
15_path_03.txt | AC | 33 ms | 4772 KB |
15_path_04.txt | AC | 35 ms | 4760 KB |
16_path_05.txt | AC | 35 ms | 4764 KB |
16_path_06.txt | AC | 36 ms | 4764 KB |
16_path_07.txt | AC | 37 ms | 4768 KB |
16_path_08.txt | AC | 36 ms | 4764 KB |
16_path_09.txt | AC | 34 ms | 4764 KB |
17_path_10.txt | AC | 1372 ms | 5400 KB |
17_path_11.txt | AC | 1293 ms | 5152 KB |
17_path_12.txt | AC | 1329 ms | 5024 KB |
17_path_13.txt | AC | 1311 ms | 5420 KB |
17_path_14.txt | AC | 1353 ms | 5412 KB |
20_random_15.txt | AC | 36 ms | 4836 KB |
20_random_16.txt | AC | 35 ms | 4772 KB |
20_random_17.txt | AC | 34 ms | 4768 KB |
21_random_18.txt | AC | 35 ms | 4768 KB |
21_random_19.txt | AC | 35 ms | 4764 KB |
21_random_20.txt | AC | 33 ms | 4764 KB |
30_random_21.txt | AC | 35 ms | 4772 KB |
30_random_22.txt | AC | 36 ms | 4756 KB |
30_random_23.txt | AC | 36 ms | 4772 KB |
40_random_24.txt | AC | 1329 ms | 4764 KB |
40_random_25.txt | AC | 1347 ms | 4704 KB |
40_random_26.txt | AC | 1230 ms | 4768 KB |
49_sample_02.txt | AC | 33 ms | 4820 KB |
61_test_27.txt | AC | 1314 ms | 5156 KB |
61_test_28.txt | AC | 1301 ms | 5024 KB |
61_test_29.txt | AC | 1303 ms | 4956 KB |
63_star_30.txt | AC | 821 ms | 4896 KB |
63_star_31.txt | AC | 790 ms | 4764 KB |
63_star_32.txt | AC | 746 ms | 4768 KB |
64_three_33.txt | AC | 1439 ms | 4896 KB |
64_three_34.txt | AC | 1452 ms | 5020 KB |
64_three_35.txt | AC | 1468 ms | 5016 KB |