#720149 (C++17) No.1769 Don't Stop the Game

提出ソース
結果

問題	No.1769 Don't Stop the Game
コンテスト
ユーザー	HIR180
提出日時	2021-11-26 23:39:35
言語	C++17 (gcc 13.3.0 + boost 1.87.0)
結果	AC
実行時間	1,352 ms / 3,000 ms
コード長	8,521 bytes
コンパイル時間	3,693 ms
コンパイル使用メモリ	211,548 KB
最終ジャッジ日時	2025-01-26 01:57:35
ジャッジサーバーID （参考情報）	judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン	結果
sample	AC * 3
other	AC * 28
権限があれば一括ダウンロードができます
ソースコード

raw source code
//Let's join Kaede Takagaki Fan Club !!
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cassert>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <functional>
#include <iostream>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <cassert>
#include <iomanip>
#include <chrono>
#include <random>
#include <bitset>
#include <complex>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
#define int long long
//#define L __int128
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 eb emplace_back
#define mp make_pair
#define eps 1e-7
#define INF 1000000000
#define a first
#define b second
#define fi first
#define sc second
#define rng(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#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()
#define si(x) int(x.size())
 
#ifdef LOCAL
#define dmp(x) cerr<<__LINE__<<" "<<#x<<" "<<x<<endl
#else
#define dmp(x) void(0)
#endif
 
template<class t,class u> bool chmax(t&a,u b){if(a<b){a=b;return true;}else return false;}
template<class t,class u> bool chmin(t&a,u b){if(b<a){a=b;return true;}else return false;}
 
template<class t> using vc=vector<t>;
 
template<class t,class u>
ostream& operator<<(ostream& os,const pair<t,u>& p){
	return os<<"{"<<p.fi<<","<<p.sc<<"}";
}
 
template<class t> ostream& operator<<(ostream& os,const vc<t>& v){
	os<<"{";
	for(auto e:v)os<<e<<",";
	return os<<"}";
}
 
 //https://codeforces.com/blog/entry/62393
struct custom_hash {
	static uint64_t splitmix64(uint64_t x) {
		// http://xorshift.di.unimi.it/splitmix64.c
		x += 0x9e3779b97f4a7c15;
		x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
		x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
		return x ^ (x >> 31);
	}
 
	size_t operator()(uint64_t x) const {
		static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
		return splitmix64(x + FIXED_RANDOM);
	}
	
	size_t operator()(pair<int,int> x)const{
		return operator()(uint64_t(x.first)<<32|x.second);
	}
};
//unordered_set -> dtype, null_type
//unordered_map -> dtype(key), dtype(value)
using namespace __gnu_pbds;
template<class t,class u>
using hash_table=gp_hash_table<t,u,custom_hash>;

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 = 998244353;
//const ll mod = 1000000007;
mt19937_64 mt(chrono::steady_clock::now().time_since_epoch().count());
template<class T>
void add(T&a,T b){
	a+=b;
	if(a >= mod) a-=mod;
}
ll modpow(ll x,ll n){
	ll res=1;
	while(n>0){
		if(n&1) res=res*x%mod;
		x=x*x%mod;
		n>>=1;
	}
	return res;
}
#define _sz 1
ll F[_sz],R[_sz];
void make(){
	F[0] = 1;
	for(int i=1;i<_sz;i++) F[i] = F[i-1]*i%mod;
	R[_sz-1] = modpow(F[_sz-1], mod-2);
	for(int i=_sz-2;i>=0;i--) R[i] = R[i+1] * (i+1) % mod;
}
ll C(int a,int b){
	if(b < 0 || a < b) return 0;
	return F[a]*R[b]%mod*R[a-b]%mod;
}
#define SZ 200005
int n;
vc<P>edge[SZ];
P ar[SZ*2]={};
int pos[SZ]={},id=0,up[SZ],dep[SZ],val[SZ];
P mn[20][SZ*2]={};
int sz[SZ*2]={};
struct LCA{
	//SZは元の木の頂点数より大
	//外部でedge[]に隣接状況を持って置く必要あり
	
	void dfs(int v,int u,int d){
		pos[v] = id; up[v] = u; val[v] = d;
		if(u == -1) dep[v] = 0;
		else dep[v] = dep[u] + 1;
		
		ar[id++] = mp(dep[v],v);
		for(int i=0;i<edge[v].size();i++){
			if(edge[v][i].a == u) continue;
			dfs(edge[v][i].a,v,d ^ edge[v][i].b);
			ar[id++] = mp(dep[v],v);
		}
	}
	void prepare(){
		dfs(1,-1,0);
		for(int i=0;i<id;i++) mn[0][i] = ar[i];
		for(int j=0;j<19;j++){
			for(int i=0;i<id;i++){
				if(i+(1<<j) >= id) mn[j+1][i] = mn[j][i];
				else mn[j+1][i] = min(mn[j][i], mn[j][i+(1<<j)]);
			}
		}
		for(int i=1;i<SZ*2;i++){
			for(int j=0;j<20;j++){
				if((1<<j) <= i && i <= (2<<j)){
					sz[i] = j;
					break;
				}
			}
		}
	}
	int get(int a,int b){
		int len = max(pos[a],pos[b]) - min(pos[a],pos[b]) + 1;
		int ty = sz[len];
		P p = min(mn[ty][min(pos[a],pos[b])], mn[ty][max(pos[a],pos[b])-(1<<ty)+1]);
		return p.second;
	}
}kaede;




struct dat {
	ll sz;
	//reverseする
	void rv(){
		//lol
	}
};
//自作コンストラクタ
dat dt(int sz){
	return {sz};
}
//a, b をこの順にマージする
dat mrg(dat a, dat b){
	return {a.sz + b.sz};
}
struct node{
	node *l, *r, *p;
	int id, rev;
	dat D, S, L;
	node(int i, ll v) : l(0), r(0), p(0), id(i), rev(0){
		//Dに実データを持つ
		//Sに自分のデータを持つ
		//Lにはlight edgeでつながっている部分木のデータを持つ
		D = S = dt(v);
		L = dt(0);
	}
};

inline bool is_root(node *n){
	return n -> p == NULL || n -> p -> l != n && n -> p -> r != n;
}

inline bool left(node *n){
	return n == n -> p -> l;
}

//遅延評価
//push(n)を走らせた後にはn->l と n->r の値は正しく計算されている必要あり
inline 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;
	}
}

//値の再計算
inline void update(node *n){
	//最初に遅延評価
	push(n);
	
	dat slf = mrg(n->S, n->L);
	if(n->l) slf = mrg(n->l->D, slf);
	if(n->r) slf = mrg(slf, n->r->D);
	n->D = slf;
}
inline void connect(node *n, node *p, bool l){
	(l ? p -> l : p -> r) = n;
	if(n) n -> p = p;
}
//rotateが呼ばれる前には関与しているノードの遅延評価をする必要がある
inline void rotate(node *n){
	node *p = n -> p, *g = p -> p;
	bool l = left(n);
	connect(l ? n -> r : n -> l, p, l);
	if(!is_root(p)) connect(n, g, left(p));
	else n -> p = g;
	connect(p, n, !l);
	update(p), update(n);
}
inline void splay(node *n){
	while(!is_root(n)){
		node *p = n -> p, *g = p -> p;
		//関与する頂点群の遅延評価をする
		if(!is_root(p)) push(g);
		push(p), push(n);
		if(!is_root(p)) rotate(left(n) ^ left(p) ? n : p);
		rotate(n);
	}
	//最後に遅延評価
	push(n);
}
//返り値はnじゃないよ
//部分木クエリの時はLを修正しようね！
inline node* expose(node *n){
	node *last = NULL;
	for(node *m = n; m; m = m -> p){
		splay(m);
		m->L.sz += (m->r ? m->r->D.sz : 0);
		m -> r = last;
		m->L.sz -= (m->r ? m->r->D.sz : 0);
		update(m);
		last = m;
	}
	splay(n);
	return last;
}
//部分木クエリの時はLを修正しようね！
inline void link(node *m, node *n){
	expose(m), expose(n);
	m -> p = n;
	n->L.sz += m->D.sz;
	update(n);
}
inline void cut(node *n){
	expose(n);
	n -> l -> p = NULL;
	n -> l = NULL;
	update(n);
}
//nを根に持っていく
//updateは必要ない
inline void evert(node *n){
	expose(n);
	n->rev ^= 1;
	n->D.rv();
}

//u-v切断: evert(V[u]) cut(V[v])
//u-v接続: evert(V[u]) link(V[u], V[v])
//点更新は: evert(V[v]) update(V[x])
//u-vパスクエリ: evert(V[u]) expose(V[v]) update(V[v]) でV[v]->Dを見る


const int MAXN = 200005;
node *V[MAXN];
void solve(){
	cin>>n;
	repn(i, n){
		V[i] = new node(i, 1);
	}
	
	rep(i, n-1){
		int a, b, c; cin >> a >> b >> c;
		edge[a].eb(b, c);
		edge[b].eb(a, c);
		evert(V[a]);
		link(V[a], V[b]);
	}
	kaede.prepare();
	map<int, vector<int>>M;
	repn(i, n){
		M[val[i]].pb(i);
	}
	int ans = 0;
	for(auto a:M){
		auto ls = a.b;
		for(auto v:ls){
			for(auto x:edge[v]){
				if(val[v] == a.a and val[x.a] == a.a and v < x.a) continue;
              	{
					evert(V[v]);
					cut(V[x.a]);
				}
			}
		}
		for(auto v:ls){
			if(val[v] != a.a) continue;
			for(auto x:edge[v]){
				if(val[x.a] != a.a){
					evert(V[v]);
					link(V[v], V[x.a]);
				}
			}
          	evert(V[v]);
			ans += V[v]->D.sz - 1;
			for(auto x:edge[v]){
				if(val[x.a] != a.a){
					evert(V[v]);
					cut(V[x.a]);
				}
			}
		}
		for(auto v:ls){
			for(auto x:edge[v]){
				if(val[v] == a.a and val[x.a] == a.a and v < x.a) continue;
              	{
					evert(V[v]);
					link(V[v], V[x.a]);
				}
			}
		}
	}
	o(ans);
}
signed main(){
	cin.tie(0);
	ios::sync_with_stdio(0);
	cout<<fixed<<setprecision(20);
	int t; t=1;//cin >> t;
	while(t--) solve();
}
yukicoder

結果

ソースコード
