結果
問題 | No.772 Dynamic Distance Sum |
ユーザー | chocorusk |
提出日時 | 2020-04-01 10:37:03 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 1,219 ms / 5,000 ms |
コード長 | 4,655 bytes |
コンパイル時間 | 1,571 ms |
コンパイル使用メモリ | 121,644 KB |
実行使用メモリ | 48,820 KB |
最終ジャッジ日時 | 2024-06-26 06:09:49 |
合計ジャッジ時間 | 24,618 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
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 | 7 ms
5,376 KB |
testcase_05 | AC | 4 ms
5,376 KB |
testcase_06 | AC | 6 ms
5,376 KB |
testcase_07 | AC | 4 ms
5,376 KB |
testcase_08 | AC | 5 ms
5,376 KB |
testcase_09 | AC | 7 ms
5,376 KB |
testcase_10 | AC | 6 ms
5,376 KB |
testcase_11 | AC | 3 ms
5,376 KB |
testcase_12 | AC | 1,219 ms
42,524 KB |
testcase_13 | AC | 1,169 ms
40,996 KB |
testcase_14 | AC | 1,195 ms
44,900 KB |
testcase_15 | AC | 871 ms
40,244 KB |
testcase_16 | AC | 1,063 ms
42,604 KB |
testcase_17 | AC | 1,168 ms
42,264 KB |
testcase_18 | AC | 710 ms
44,500 KB |
testcase_19 | AC | 1,165 ms
41,080 KB |
testcase_20 | AC | 659 ms
45,156 KB |
testcase_21 | AC | 1,181 ms
45,816 KB |
testcase_22 | AC | 1,079 ms
45,044 KB |
testcase_23 | AC | 1,215 ms
48,820 KB |
testcase_24 | AC | 897 ms
42,856 KB |
testcase_25 | AC | 1,093 ms
45,796 KB |
testcase_26 | AC | 1,114 ms
45,724 KB |
testcase_27 | AC | 939 ms
46,220 KB |
testcase_28 | AC | 1,070 ms
45,180 KB |
testcase_29 | AC | 667 ms
48,820 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; multiset<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(pp->dat.find({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(now->dat.find({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){//c:root expose(c); expose(p); p->r=c; c->p=p; update(p); } void cut(Node *c){//c->l != nullptr 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:0)>=m){ now=now->r; }else if(now->l && (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+1)/2){ evert(now); return now; }else{ /*m-=now->val; if(now->r) m-=now->r->sz;*/ 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; 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); 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 if(t==3){ 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]); ll ans=g->sum-g->cost*g->sz; //cout<<g->idx<<" "; printf("%lld\n", ans); (s+=ans)%=n; }else{ return 0; } } return 0; }