結果
問題 | No.772 Dynamic Distance Sum |
ユーザー | chocorusk |
提出日時 | 2020-04-01 10:55:22 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 1,220 ms / 5,000 ms |
コード長 | 4,499 bytes |
コンパイル時間 | 1,522 ms |
コンパイル使用メモリ | 125,540 KB |
実行使用メモリ | 49,484 KB |
最終ジャッジ日時 | 2024-06-26 06:40:31 |
合計ジャッジ時間 | 22,647 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 2 ms
5,376 KB |
testcase_02 | AC | 2 ms
5,376 KB |
testcase_03 | AC | 2 ms
5,376 KB |
testcase_04 | AC | 8 ms
5,376 KB |
testcase_05 | AC | 4 ms
5,376 KB |
testcase_06 | AC | 6 ms
5,376 KB |
testcase_07 | AC | 3 ms
5,376 KB |
testcase_08 | AC | 5 ms
5,376 KB |
testcase_09 | AC | 8 ms
5,376 KB |
testcase_10 | AC | 7 ms
5,376 KB |
testcase_11 | AC | 4 ms
5,376 KB |
testcase_12 | AC | 1,189 ms
42,956 KB |
testcase_13 | AC | 1,117 ms
41,572 KB |
testcase_14 | AC | 1,196 ms
45,584 KB |
testcase_15 | AC | 985 ms
40,800 KB |
testcase_16 | AC | 1,040 ms
43,176 KB |
testcase_17 | AC | 1,138 ms
42,960 KB |
testcase_18 | AC | 679 ms
45,064 KB |
testcase_19 | AC | 1,135 ms
41,620 KB |
testcase_20 | AC | 622 ms
45,584 KB |
testcase_21 | AC | 1,179 ms
46,352 KB |
testcase_22 | AC | 1,035 ms
45,636 KB |
testcase_23 | AC | 1,220 ms
49,352 KB |
testcase_24 | AC | 860 ms
43,388 KB |
testcase_25 | AC | 1,027 ms
46,212 KB |
testcase_26 | AC | 1,093 ms
46,148 KB |
testcase_27 | AC | 961 ms
46,860 KB |
testcase_28 | AC | 1,066 ms
45,764 KB |
testcase_29 | AC | 657 ms
49,484 KB |
ソースコード
#include <cstdio> #include <cstring> #include <iostream> #include <string> #include <cmath> #include <bitset> #include <vector> #include <map> #include <set> #include <queue> #include <deque> #include <algorithm> #include <complex> #include <unordered_map> #include <unordered_set> #include <random> #include <cassert> #include <fstream> #include <utility> #include <functional> #include <time.h> #include <stack> #include <array> #define popcount __builtin_popcount using namespace std; typedef long long int ll; typedef pair<ll, ll> P; struct LinkCutTree{ struct Node{ Node *l, *r, *p; bool rev; int idx, val, sz, szl; ll cost, sum, suml, costs, sum2; set<pair<int, int>> dat; Node(int val, int idx, ll cost):cost(cost), costs(cost), sum(0), sum2(0), suml(0), idx(idx), val(val), sz(val), szl(0), rev(false), l(nullptr), r(nullptr), p(nullptr){} bool is_root(){ return !p || (p->l!=this && p->r!=this); } }; vector<Node*> v; LinkCutTree(int n){ v.resize(n); for(int i=0; i<n; i++) v[i]=new Node(1, i, 0); } void toggle(Node *t){ if(!t) return; swap(t->sum, t->sum2); swap(t->l, t->r); t->rev^=true; } void push(Node *t){ if(!t) return; if(t->rev){ toggle(t->l); toggle(t->r); t->rev=false; } } void update(Node *t){ t->sz=t->val+t->szl, t->costs=t->cost; if(t->l) t->sz+=t->l->sz, t->costs+=t->l->costs; if(t->r) t->sz+=t->r->sz, t->costs+=t->r->costs; t->sum=t->suml+t->cost*t->szl; t->sum2=t->suml+t->cost*t->szl; if(t->l) t->sum+=t->l->sum, t->sum2+=t->l->sum2, t->sum+=t->l->costs*(t->val+t->szl), t->sum2+=t->l->sz*t->cost; if(t->r) t->sum+=t->r->sum, t->sum2+=t->r->sum2, t->sum+=t->r->sz*t->cost, t->sum2+=t->r->costs*(t->val+t->szl); if(t->l && t->r) t->sum+=t->l->costs*t->r->sz, t->sum2+=t->r->costs*t->l->sz; } void rotate(Node *t){ Node *p=t->p, *pp=p->p, *ch; if(p->l==t) ch=t->r; else ch=t->l; if(pp){ if(pp->l==p) pp->l=t; else if(pp->r==p) pp->r=t; else{ pp->dat.erase({p->sz, p->idx}); pp->dat.insert({p->sz, t->idx}); } } t->p=pp; if(p->l==t) t->r=p; else t->l=p; p->p=t; if(p->l==t) p->l=ch; else p->r=ch; if(ch) ch->p=p; update(p); update(t); } int state(Node *t){ if(t->is_root()) return 0; else if(t->p->l==t) return 1; else return -1; } void splay(Node *t){ push(t); while(state(t)){ if(!state(t->p)){ push(t->p); push(t); rotate(t); }else{ push(t->p->p); push(t->p); push(t); if(state(t->p)==state(t)){ rotate(t->p); rotate(t); }else{ rotate(t); rotate(t); } } } } Node *expose(Node *t){ Node *rp=nullptr; for(Node *now=t; now; now=now->p){ splay(now); if(rp){ now->dat.erase({rp->sz, rp->idx}); now->szl-=rp->sz; now->suml-=rp->sum; } if(now->r){ now->dat.insert({now->r->sz, now->r->idx}); now->szl+=now->r->sz; now->suml+=now->r->sum; } now->r=rp; update(now); rp=now; } splay(t); return rp; } void link(Node *c, Node *p){ expose(c); expose(p); p->r=c; c->p=p; update(p); } void cut(Node *c){ expose(c); c->l->p=nullptr; c->l=nullptr; update(c); } void evert(Node *t){ expose(t); toggle(t); push(t); } Node *find(Node *t){ evert(t); int n=t->sz, m=(n+1)/2; if(n==0) return t; Node *now=t; while(1){ push(now); if(now->r && now->r->sz>=m) now=now->r; else if((now->r?now->r->sz:0)+now->szl+now->val<m){ m-=(now->r?now->r->sz:0)+now->szl+now->val; now=now->l; }else{ if(now->dat.empty() || (*now->dat.rbegin()).first<=n/2) return now; else{ m=(n+1)/2; now=v[(*now->dat.rbegin()).second]; } } } } }; int main() { int n, q; scanf("%d %d", &n, &q); LinkCutTree lct(n); using node=LinkCutTree::Node; ll s=0; int k=n; int a1[300030]; while(q--){ int t; scanf("%d", &t); if(t==1){ int a, b, c; scanf("%d %d %d", &a, &b, &c); a=(a-1+s)%n, b=(b-1+s)%n; node *e=new node(0, k, c); a1[k]=a; k++; lct.v.push_back(e); lct.link(e, lct.v[a]); lct.evert(e); lct.link(e, lct.v[b]); }else if(t==2){ int a, b; scanf("%d %d", &a, &b); a=(a-1+s)%n, b=(b-1+s)%n; lct.evert(lct.v[a]); lct.expose(lct.v[b]); lct.cut(lct.v[b]); }else{ int a; scanf("%d", &a); a=(a-1+s)%n; lct.expose(lct.v[a]); lct.v[a]->val^=1; node *g=lct.find(lct.v[a]); if(g->idx>=n) g=lct.v[a1[g->idx]]; lct.evert(g); ll ans=g->sum; printf("%lld\n", ans); (s+=ans)%=n; } } return 0; }