結果

問題 No.772 Dynamic Distance Sum
コンテスト
ユーザー HIR180
提出日時 2020-04-14 15:06:43
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 7,798 bytes
コンパイル時間 2,970 ms
コンパイル使用メモリ 230,344 KB
最終ジャッジ日時 2025-01-09 18:39:58
ジャッジサーバーID
（参考情報） 		judge2 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample WA * 1 RE * 1 TLE * 1
other WA * 1 RE * 3 OLE * 23
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:277:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  277 |         scanf("%d%d",&n, &q);
      |         ~~~~~^~~~~~~~~~~~~~~
main.cpp:282:30: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  282 |                 int ty; scanf("%d",&ty);
      |                         ~~~~~^~~~~~~~~~
main.cpp:284:43: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  284 |                         int a, b, c; scanf("%d%d%d",&a,&b,&c);
      |                                      ~~~~~^~~~~~~~~~~~~~~~~~~
main.cpp:300:40: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  300 |                         int a, b; scanf("%d%d",&a,&b);
      |                                   ~~~~~^~~~~~~~~~~~~~
main.cpp:311:37: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  311 |                         int a; scanf("%d",&a);
      |                                ~~~~~^~~~~~~~~

ソースコード

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){
		node *q = n->p, *g = q->p;
		if((q->l = n->r)) n->r->p = q;
		n->r = q; q->p = n;
		update(q); update(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(n->D.cnt1, q->id));
				g->L_sz.insert(mp(n->D.cnt1, n->id));
			}
			update(g);
		}
	}
	//左回転
	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;
		update(q); update(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(n->D.cnt1, q->id));
				g->L_sz.insert(mp(n->D.cnt1, n->id));
			}
			update(g);
		}
	}
	//スプレー操作
	void splay(node *n){
	    push(n);
		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);
				}
			}
			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);
					}
				}
			}
		}
	}
	
	vector<node*>pool;
	//本質
	//xから根までのパスを形成
	node *expose(node *x){
		node *rr = (node *)NULL;
		for(node *pp = x;pp;pp = pp->p){
			//今いるところをsplay
			splay(pp);
			//右にさっきまでの木を繋げる
			if(pp->r){
				pp->L.cnt1 += pp->r->D.cnt1;
				pp->L.sum1 += pp->r->D.sum1;
				pp->L_sz.insert(mp(pp->r->D.cnt1, pp->r->id));
			}
			pp->r = rr;
			if(pp->r){
				pp->L.cnt1 -= pp->r->D.cnt1;
				pp->L.sum1 -= pp->r->D.sum1;
				pp->L_sz.erase(mp(pp->r->D.cnt1, pp->r->id));
			}
			//覚えておく
			update(pp);
			rr = pp;
		}
		splay(x);
		return rr;
	}
	node *find_root(node *n){
		if(!n) return (node*)NULL;
		while(1){ push(n); if(n->r) n = n->r; else return n; }
	}
	node *cut(node *c){
		expose(c);
		node *p = c->l;
		c->l->p = NULL;
		c->l = NULL;
		update(c);
		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;
		cout << n->id << " " << (n->l?n->l->id:-1) << " " << (n->r?n->r->id:-1) << " " << n->L.cnt1 << " " << n->L.sum1 << endl;
	}
	//非連結なら-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<=798;i++){
			if(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);
		cout << n->id <<"ID " << endl;
		cout << n->D.sum1 << " " << n->D.sum2 << endl;
		n->rev ^= 1;
		n->D.rv();
		cout << n->D.sum1 << " " << n->D.sum2 << endl;
	}
}kaede;

int n, q;
ll sum;
int nxt = 100001;
int main(){
	scanf("%d%d",&n, &q);
	kaede.pool.resize(400005, new LinkCutTree::node(0, 0, 0));
	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;
			cout << a << " d " << b << endl;
			kaede.evert(kaede.pool[a]);
			cout << kaede.pool[a]->D.sum1 << endl;
			kaede.pool[nxt] = new LinkCutTree::node(nxt, 0, c);
			cout << kaede.pool[nxt]->D.sum1 << endl;
			kaede.link(kaede.pool[a], kaede.pool[nxt]);
			kaede.link(kaede.pool[nxt], kaede.pool[b]); nxt++;
			for(int i=1;i<=n;i++){
			    kaede.evert(kaede.pool[i]);
			    cout << kaede.pool[i]->id << " = " << i << endl;
			    cout << i << " " << kaede.pool[i]->D.sum1 << " " << kaede.pool[i]->D.cnt1 << " " << kaede.pool[i]->D.sum << endl;
			}
		}
		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);
			for(int i=1;i<=n;i++){
			    kaede.evert(kaede.pool[i]);
			    cout << i << " " << kaede.pool[i]->D.sum1 << endl;
			}
		}
		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]);
			cout << kaede.pool[a]->D.cnt1 << " " << kaede.pool[a]->D.sum1 << " " << kaede.pool[a]->D.sum2 << endl;
			ll ans;
			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