#464238 (C++17) No.772 Dynamic Distance Sum

提出ソース

結果

問題	No.772 Dynamic Distance Sum
ユーザー	HIR180
提出日時	2020-04-14 20:58:50
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	TLE
実行時間	-
コード長	6,491 bytes
コンパイル時間	3,609 ms
コンパイル使用メモリ	229,120 KB
実行使用メモリ	12,668 KB
最終ジャッジ日時	2024-04-09 18:08:57
合計ジャッジ時間	11,473 ms
ジャッジサーバーID （参考情報）	judge1 / judge3

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,820 KB
testcase_01	AC	2 ms 6,944 KB
testcase_02	AC	2 ms 6,944 KB
testcase_03	AC	2 ms 6,940 KB
testcase_04	TLE	-
testcase_05	--	-
testcase_06	--	-
testcase_07	--	-
testcase_08	--	-
testcase_09	--	-
testcase_10	--	-
testcase_11	--	-
testcase_12	--	-
testcase_13	--	-
testcase_14	--	-
testcase_15	--	-
testcase_16	--	-
testcase_17	--	-
testcase_18	--	-
testcase_19	--	-
testcase_20	--	-
testcase_21	--	-
testcase_22	--	-
testcase_23	--	-
testcase_24	--	-
testcase_25	--	-
testcase_26	--	-
testcase_27	--	-
testcase_28	--	-
testcase_29	--	-

権限があれば一括ダウンロードができます

ソースコード

raw source code

//Let's join Kaede Takagaki Fan Club !!
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef pair<int,P> P1;
typedef pair<P,P> P2;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define INF 1000000000
#define fi first
#define sc second
#define rep(i,x) for(int i=0;i<x;i++)
#define repn(i,x) for(int i=1;i<=x;i++)
#define SORT(x) sort(x.begin(),x.end())
#define ERASE(x) x.erase(unique(x.begin(),x.end()),x.end())
#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin())
#define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin())
#define all(x) x.begin(),x.end()
template<class T>
void dmp(T a){
	rep(i,a.size()) cout << a[i] << " ";
	cout << endl;
}
template<class T>
bool chmax(T&a, T b){
	if(a < b){
		a = b;
		return 1;
	}
	return 0;
}
template<class T>
bool chmin(T&a, T b){
	if(a > b){
		a = b;
		return 1;
	}
	return 0;
}
template<class T>
void g(T &a){
	cin >> a;
}
template<class T>
void o(const T &a,bool space=false){
	cout << a << (space?' ':'\n');
}
//ios::sync_with_stdio(false);
const ll mod = 1000000007;//998244353
template<class T>
void add(T&a,T b){
	a+=b;
	if(a >= mod) a-=mod;
}


struct LinkCutTree{
	struct dat {
		int cnt1;
		ll sum, sum1, sum2;
		void rv(){ swap(sum1, sum2); }
	};
	struct node{
		node *p,*l,*r; //親、左の子、右の子
		int id, rev;
		dat D, L, S;
		multiset<P, greater<P>>L_sz;
		node(int i, int c, int w) : l(0), r(0), p(0), id(i), rev(0) {
			D = S = {c, w, w, w};
			L = {0, 0, 0, 0};
			L_sz.clear();
		}
		//このノードはsplay木の根？ (=今いるパスの最上頂点？)
		bool is_root(){
			return !p || (p->l != this && p->r != this);
		}
	};
	//右回転
	void rotr(node *n){
		node *q = n->p, *g = q->p;
		if((q->l = n->r)) n->r->p = q;
		n->r = q; q->p = n;
		if((n->p = g)){
			if(g->l == q) g->l = n;
			else if(g->r == q) g->r = n;
			else{
				g->L_sz.erase(mp(q->D.cnt1, q->id));
				g->L_sz.insert(mp(q->D.cnt1, n->id));
			}
		}
	}
	//左回転
	void rotl(node *n){
		node *q = n->p, *g = q->p;
		if((q->r = n->l)) n->l->p = q;
		n->l = q; q->p = n;
		if((n->p = g)){
			if(g->l == q) g->l = n;
			else if(g->r == q) g->r = n;
			else{
				g->L_sz.erase(mp(q->D.cnt1, q->id));
				g->L_sz.insert(mp(q->D.cnt1, n->id));
			}
		}
	}
	//スプレー操作
	void splay(node *n){
	    if(n->is_root()) {
	        update(n); return;
	    }
		while(!n->is_root()){
			node *q = n->p;
			//自分の親がroot、zig
			if(q->is_root()){
			    push(q); push(n);
				if(q->l == n){
					rotr(n);
				}
				else{
					rotl(n);
				}
				update(q); update(n);
			}
			else{
				node *r = q->p;
				push(r); push(q); push(n);
				if(r->l == q){
					if(q->l == n){
						//zig-zig
						rotr(q);
						rotr(n);
					}
					else{
						//zig-zag
						rotl(n);
						rotr(n);
					}
				}
				else{
					if(q->r == n){
						//zig-zig
						rotl(q);
						rotl(n);
					}
					else{
						//zig-zag
						rotr(n);
						rotl(n);
					}
				}
				update(r); update(q); update(n);
			}
		}
	}
	
	node *pool[400005];
	//本質
	//xから根までのパスを形成
	node *expose(node *x){
		node *r = (node *)NULL;
		for(node *p = x;p;p = p->p){
			//今いるところをsplay
			splay(p);
			//右にさっきまでの木を繋げる
			if(p->r){
				p->L.cnt1 += p->r->D.cnt1;
				p->L.sum1 += p->r->D.sum1;
				p->L_sz.insert(mp(p->r->D.cnt1, p->r->id));
			}
			p->r = r;
			if(p->r){
				p->L.cnt1 -= p->r->D.cnt1;
				p->L.sum1 -= p->r->D.sum1;
				p->L_sz.erase(mp(p->r->D.cnt1, p->r->id));
			}
			//覚えておく
			update(p);
			r = p;
		}
		splay(x);
		return r;
	}
	node *find_root(node *n){
		if(!n) return NULL;
		while(1){ push(n); if(n->r) n = n->r; else return n; }
	}
	node *cut(node *n){
	    expose(n);
		node *p = n->l;
		n->l->p = NULL;
		n->l = NULL;
		update(n);
		return find_root(p);
	}
	void link(node *c, node *p){
		expose(c); expose(p);
		c->p = p;
		p->r = c;
		update(p);
	}
	void push(node *n){
		if(n->rev){
			swap(n->l, n->r);
			if(n->l) n->l->rev ^= 1, n->l->D.rv();
			if(n->r) n->r->rev ^= 1, n->r->D.rv();
			n->rev = 0;
		}
	}
	void update(node *n){
		push(n);
		
		n->D.cnt1 = (n->l?n->l->D.cnt1:0) + (n->r?n->r->D.cnt1:0) + n->L.cnt1 + n->S.cnt1;
		n->D.sum = (n->l?n->l->D.sum:0) + (n->r?n->r->D.sum:0) + n->S.sum;
		n->D.sum1 = 0;
		if(n->l) n->D.sum1 += n->l->D.sum1;
		if(n->r) n->D.sum1 += n->r->D.sum1 + 1LL*(n->S.sum+(n->l?n->l->D.sum:0)) * n->r->D.cnt1;
		if(n->S.cnt1) n->D.sum1 += 1LL*(n->S.sum+(n->l?n->l->D.sum:0));
		n->D.sum1 += n->L.sum1 + 1LL*(n->S.sum+(n->l?n->l->D.sum:0)) * n->L.cnt1;
		
		n->D.sum2 = 0;
		if(n->l) n->D.sum2 += n->l->D.sum2 + 1LL*(n->S.sum+(n->r?n->r->D.sum:0)) * n->l->D.cnt1;
		if(n->r) n->D.sum2 += n->r->D.sum2;
		if(n->S.cnt1) n->D.sum2 += 1LL*(n->S.sum+(n->r?n->r->D.sum:0));
		n->D.sum2 += n->L.sum1 + 1LL*(n->S.sum+(n->r?n->r->D.sum:0)) * n->L.cnt1;
	}
	int find(node *n, int sz){
		int lim = (sz+1)/2;
		while(1){
			push(n);
			if(n->r && n->r->D.cnt1 >= lim) n = n->r;
			else if(n->l && n->D.cnt1 - n->l->D.cnt1 < lim){
			    lim -= (n->D.cnt1-n->l->D.cnt1); n = n->l; 
			}
			else if(n->L_sz.size() && (*n->L_sz.begin()).fi >= (sz+1)/2){
				lim = (sz+1)/2; n = pool[(*n->L_sz.begin()).sc];
			}
			else return n->id;
		}
	}
	void evert(node *n){
		expose(n);
		n->rev ^= 1;
		n->D.rv();
	}
}kaede;

int n, q;
ll sum;
int nxt = 100001;
int main(){
	scanf("%d%d",&n, &q);
	repn(i, n) kaede.pool[i] = new LinkCutTree::node(i, 1, 0);
	rep(i, q){
		int ty; scanf("%d",&ty);
		if(ty == 1){
			int a, b, c; scanf("%d%d%d",&a,&b,&c);
			a = (a-1+sum)%n+1; b = (b-1+sum)%n+1;
			kaede.evert(kaede.pool[a]);
			kaede.pool[nxt] = new LinkCutTree::node(nxt, 0, c);
			kaede.link(kaede.pool[a], kaede.pool[nxt]);
			kaede.link(kaede.pool[nxt], kaede.pool[b]); nxt++;
		}
		else if(ty == 2){
			int a, b; scanf("%d%d",&a,&b);
			a = (a-1+sum)%n+1; b = (b-1+sum)%n+1;
			kaede.evert(kaede.pool[a]);
			auto *mid = kaede.cut(kaede.pool[b]);
			kaede.cut(mid);
		}
		else{
			int a; scanf("%d",&a);
			a = (a-1+sum)%n+1;
			kaede.evert(kaede.pool[a]); kaede.pool[a]->S.cnt1 ^= 1; kaede.update(kaede.pool[a]);
			ll ans = 1e18;
			if(kaede.pool[a]->D.cnt1 == 0){
				ans = 0;
			}
			else{
				int cent = kaede.find(kaede.pool[a], kaede.pool[a]->D.cnt1);
				kaede.evert(kaede.pool[cent]); ans = kaede.pool[cent]->D.sum1;
			}
			printf("%lld\n", ans);
			sum = (sum+ans)%n;
		}
	}
}

yukicoder

結果

テストケース

ソースコード