結果

問題 No.772 Dynamic Distance Sum
ユーザー HIR180HIR180
提出日時 2020-04-14 21:47:21
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 1,546 ms / 5,000 ms
コード長 7,429 bytes
コンパイル時間 2,904 ms
コンパイル使用メモリ 234,348 KB
実行使用メモリ 116,352 KB
最終ジャッジ日時 2024-10-01 18:12:54
合計ジャッジ時間 28,806 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 68 ms
81,792 KB
testcase_01 AC 66 ms
81,792 KB
testcase_02 AC 69 ms
81,792 KB
testcase_03 AC 68 ms
81,792 KB
testcase_04 AC 79 ms
82,128 KB
testcase_05 AC 74 ms
81,920 KB
testcase_06 AC 74 ms
81,984 KB
testcase_07 AC 71 ms
81,792 KB
testcase_08 AC 68 ms
81,944 KB
testcase_09 AC 82 ms
82,048 KB
testcase_10 AC 74 ms
82,156 KB
testcase_11 AC 75 ms
81,792 KB
testcase_12 AC 1,546 ms
112,384 KB
testcase_13 AC 1,495 ms
111,744 KB
testcase_14 AC 1,435 ms
114,860 KB
testcase_15 AC 996 ms
112,000 KB
testcase_16 AC 1,287 ms
112,768 KB
testcase_17 AC 1,446 ms
112,548 KB
testcase_18 AC 809 ms
114,688 KB
testcase_19 AC 1,403 ms
112,000 KB
testcase_20 AC 719 ms
114,816 KB
testcase_21 AC 1,490 ms
113,008 KB
testcase_22 AC 1,301 ms
112,256 KB
testcase_23 AC 1,489 ms
116,352 KB
testcase_24 AC 1,002 ms
112,896 KB
testcase_25 AC 1,267 ms
113,536 KB
testcase_26 AC 1,365 ms
113,280 KB
testcase_27 AC 1,130 ms
114,132 KB
testcase_28 AC 1,369 ms
112,512 KB
testcase_29 AC 749 ms
116,352 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function 'int main()':
main.cpp:287:39: warning: iteration 400004 invokes undefined behavior [-Waggressive-loop-optimizations]
  287 |         repn(i, 400005) kaede.pool[i] = new LinkCutTree::node(i, 1, 0);
      |                         ~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
main.cpp:18:32: note: within this loop
   18 | #define repn(i,x) for(int i=1;i<=x;i++)
      |                                ^
main.cpp:287:9: note: in expansion of macro 'repn'
  287 |         repn(i, 400005) kaede.pool[i] = new LinkCutTree::node(i, 1, 0);
      |         ^~~~

ソースコード

diff # 

//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, int sz){
		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(sz, q->id));
				g->L_sz.insert(mp(sz, n->id));
			}
		}
	}
	//左回転
	void rotl(node *n, int sz){
		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(sz, q->id));
				g->L_sz.insert(mp(sz, 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);
			    int X = q->D.cnt1;
				if(q->l == n){
					rotr(n, X);
				}
				else{
					rotl(n, X);
				}
				update(q); update(n);
				assert(n->D.cnt1 == X);
			}
			else{
				node *r = q->p;
				push(r); push(q); push(n);
				int X = r->D.cnt1;
				if(r->l == q){
					if(q->l == n){
						//zig-zig
						rotr(q, X), rotr(n, X);
					}
					else{
						//zig-zag
						rotl(n, X), rotr(n, X);
					}
				}
				else{
					if(q->r == n){
						//zig-zig
						rotl(q, X);rotl(n, X);
					}
					else{
						//zig-zag
						rotr(n, X);rotl(n, X);
					}
				}
				update(r); update(q); update(n);
				assert(n->D.cnt1 == X);
			}
		}
	}
	
	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;
		}
	}*/
	//非連結なら-1
	int LCA(node *a,node *b){
		if(a->id == b->id) return a->id;
		expose(a);
		node *ret = expose(b);
		if(a->p == (node*)NULL) return -1;
		else return ret->id;
	}
	int find(node *n, int sz){
		/*pair<ll,int>mn = mp(8e18, -1);
		for(int i=1;i<=1000;i++){
			if(pool[i]->id != i || LCA(n, pool[i]) == -1) continue;
			evert(pool[i]);
			mn = min(mn, mp(pool[i]->D.sum1, i));
		}
		//cout << "ANSWER" << " " << mn.fi << " " << mn.sc << endl;
		return mn.sc;*/
	    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, 400005) 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;
		}
	}
}
0