Submission #22884

#	Time	Username	Problem	Language	Result	Execution time	Memory
22884		AcornCkiGs14004Team (#40)	Logistical Metropolis (KRIII5_LM)	C++11	2 / 7	2000 ms	85348 KiB

LM

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <memory.h>
#include <math.h>
#include <assert.h>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <algorithm>
#include <iostream>
#include <functional>

using namespace std;
typedef long long ll;
typedef pair<int, int> Pi;
#define Fi first
#define Se second
#define pb(x) push_back(x)
#define sz(x) (int)x.size()
#define rep(i, n) for(int i=0;i<n;i++)
#define all(x) x.begin(), x.end()
typedef pair<int, int> pii;
typedef tuple<int, int, int> t3;

struct node{
	node(){}
	node(int x){
		idx = x;
		rev = val = 0; mx = Pi(0, x);
		child[0] = child[1] = par = pp = 0;
	}
	Pi mx;
	int val, idx, rev;
	node *child[2], *par, *pp;
	inline int mydir(){
		return par->child[1] == this;
	}
	inline void pushdown(){
		if(rev){
			swap(child[0], child[1]);
			if(child[0])child[0]->rev ^= 1;
			if(child[1])child[1]->rev ^= 1;
			rev = 0;
		}
	}
	inline void pushup(){
		mx.Fi = val, mx.Se = idx;
		if(child[0] && child[0]->mx.Fi > mx.Fi)mx = child[0]->mx;
		if(child[1] && child[1]->mx.Fi > mx.Fi)mx = child[1]->mx;
	}
	void rotate(int dir){
		node *c = child[!dir];
		c->pushdown();
		if(par)par->child[mydir()] = c; c->par = par;
		if(pp)c->pp = pp, pp = 0;
		child[!dir] = c->child[dir];
		if(c->child[dir])c->child[dir]->par = this;
		c->child[dir] = this;
		par = c;
		pushup();
		c->pushup();
	}
	void splay(node *rootp){
		while(par != rootp){
			if(par->par == rootp){
				par->pushdown();
				par->rotate(!mydir());
			}
			else{
				par->par->pushdown();
				par->pushdown();
				int md = mydir();
				if(par->mydir() != md){
					par->rotate(!md);
					par->rotate(md);
				}
				else{
					par->par->rotate(!md);
					par->rotate(!md);
				}
			}
		}
	}
};

node *mem[1000010];
pii meme[1000040];

void access(node *v){
	v->splay(0); v->pushdown();
	if(v->child[1]){
		v->child[1]->par = 0, v->child[1]->pp = v;
		v->child[1] = 0; v->pushup();
	}
	while(v->pp){
		node *u = v->pp;
		u->splay(0); u->pushdown();
		if(u->child[1])u->child[1]->par = 0, u->child[1]->pp = u;
		u->child[1] = v;
		v->par = u; v->pp = 0;
		u->pushup();
		v->splay(0);
	}
}

void makeroot(node *v){
	access(v);
	v->rev ^= 1;
	v->pushdown();
}

int mz;

void link(int ux, int vx, int L){
	node *u = mem[ux];
	node *v = mem[vx];
	makeroot(v);
	++mz; mem[mz] = new node(mz);
	mem[mz]->val = L; mem[mz]->mx.Fi = L;
	meme[mz] = Pi(ux, vx);
	access(u);
	u->child[1] = mem[mz]; mem[mz]->par = u;
	mem[mz]->child[1] = v; v->par = mem[mz];
	mem[mz]->pushup(); u->pushup();
//	printf("link %d -- %d, %d\n", ux, mz, L); printf("link %d -- %d, %d\n", vx, mz, L);
}

void link2(int ux, int vx){
	node *u = mem[ux];
	node *v = mem[vx];
	makeroot(v);
	access(u);
	u->child[1] = v; v->par = u;
	v->pushup(); u->pushup();
}

void cut(int ux, int vx){
	node *u = mem[ux];
	node *v = mem[vx];
	access(u);
	v->splay(0);
	if(v->pp == u)v -> pp = 0;
	else{
		v->pushdown();
		v->child[1] = 0;
		v->pushup();
		u->par = 0;
	}
//	printf("cut %d -- %d\n", ux, vx);
}

/*
void link(int uv, int vv, int L){
	node *u = mem[uv], *v = mem[vv];
	makeroot(v);
	++mz; mem[mz] = new node(mz);
	mem[mz]->val = L; mem[mz]->mx.Fi = L;
	meme[mz] = Pi(uv, vv);
	access(u);
	u->child[1] = mem[mz]; mem[mz]->par = u;
	mem[mz]->child[1] = v; v->par = mem[mz];
	mem[mz]->pushup(); u->pushup();
}

void cut(int uv, int vv){
	node *u = mem[uv], *v = mem[vv];
	access(u);
	v->splay(0);
	if(v->pp == u){
		v->pp = 0;
	}
	else{
		v->pushdown();
		v->child[1] = 0;
		v->pushup();
		u->par = 0;
	}
}

void query(int x, int y, int l){
	node *u = mem[x], *v = mem[y];
	access(u);
	access(v);
	u->splay(0);
	Pi res;
	if(u->pp){
		res = u->mx;
		if(u->pp != v){
			node *w = u->pp;
			w->splay(0); w->pushdown();
			if(res.Fi < w->val)res = Pi(w->val, w->idx);
			if(res.Fi < w->child[1]->mx.Fi)res = w->child[1]->mx;
		}
	}
	else{
		res = Pi(u->val, u->idx);
		u->pushdown();
		if(res.Fi < u->child[1]->mx.Fi)res = u->child[1]->mx;
	}
	if(res.Fi <= l)return;
	ans -= res.Fi;
	ans += l;
	cut(res.Se, meme[res.Se].Fi);
	cut(res.Se, meme[res.Se].Se);
	link(x, y, l);
}
*/
 
int N, M;
vector <pii> E[100010];
ll ans;
int p[100010];
int Find(int x){return p[x] == x ? x : p[x] = Find(p[x]); }

void query(int x, int y, int l, ll &tans, pii &rr){
//	printf("Q%d %d\n", x, y);
	node *u = mem[x], *v = mem[y];
	access(u);
	access(v);
	u->splay(0);
	Pi res;
	if(u->pp){
		res = u->mx;
		if(u->pp != v){
			node *w = u->pp;
			w->splay(0); w->pushdown();
			if(res.Fi < w->val)res = Pi(w->val, w->idx);
			if(res.Fi < w->child[1]->mx.Fi)res = w->child[1]->mx;
		}
	}
	else{
		res = Pi(u->val, u->idx);
		u->pushdown();
		if(res.Fi < u->child[1]->mx.Fi)res = u->child[1]->mx;
	}
	tans -= res.Fi;
	cut(res.Se, meme[res.Se].Fi);
	cut(res.Se, meme[res.Se].Se);
	rr = res;
	link2(x, y);
}

const int INF = -1e9-10;

inline void getInt(int &a){
	a = 0;
	char c;
	while(!isdigit(c = getchar()));
	a = c - '0';
	while(isdigit(c = getchar())){
		a = a * 10 + c - '0';
	}
}

void solve(){
	getInt(N); getInt(M);
	vector <t3> V;
	rep(i, M){
		int x, y, z; getInt(x); getInt(y); getInt(z);
		if(x == y) continue;
		E[x].pb(pii(z, y));
		E[y].pb(pii(z, x));
		V.emplace_back(z, x, y);
	}
	mz = N;
	sort(all(V));
	for(int i=1;i<=N;i++)p[i] = i;
	for(int i=1;i<=N;i++)mem[i] = new node(i);
	for(int i=0;i<sz(V);i++){
		t3 &a = V[i];
		int x = Find(get<1>(a)), y = Find(get<2>(a));
		if(x != y){
			p[x] = y, ans += get<0>(a);
			int u = get<1>(a), v = get<2>(a);
			if(u > v)swap(u, v);
			link(u, v, get<0>(a));
		}
	}
	for(int i=1;i<=N;i++){
		ll tans = ans;
		vector <t3> W;
		rep(j, sz(E[i])){
			auto &e = E[i][j];
			tans += e.Fi;
			pii rr;
			query(i, e.Se, INF, tans, rr);
			int L = rr.Fi, x = meme[rr.Se].Fi, y = meme[rr.Se].Se;
			W.emplace_back(x, y, L);
		}
		rep(j, sz(E[i])){
			cut(i, E[i][j].Se);
		}
		for(t3 &e : W) link(get<0>(e), get<1>(e), get<2>(e));
		printf("%lld\n", tans);
		
	}
}

int main(){
	int Tc = 1; //scanf("%d\n", &Tc);
	for(int tc=1;tc<=Tc;tc++){
		solve();
	}
	return 0;
}

• Subtask 1: 2 / 2
• Subtask 2: 0 / 5