oj.uz

답안 #22852

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
22852 2017-04-30T07:51:55 Z AcornCkiGs14004Team(#953, gs14004, cki86201, dotorya) Logistical Metropolis (KRIII5_LM) C++14
2 / 7
 2000 ms 152912 KB 
#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[2000010];
pii meme[2000040];

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 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;
	link(x, y, l);
}

const int INF = -1e9-10;

set <pii> S;

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

void solve(){
	scanf("%d%d", &N, &M);
	vector <t3> V;
	rep(i, M){
		int x, y, z; scanf("%d%d%d", &x, &y, &z);
		if(x == y) continue;
		S.insert(pii(x, y));
		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;
		vector <int> WX; WX.resize(sz(E[i]));
		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;
			WX[j] = mz;
			W.emplace_back(x, y, L);
		}
		rep(j, sz(E[i])){
			int x = WX[j];
			cut(i, x);
			cut(E[i][j].Se, x);
		}
		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;
}

Compilation message

LM.cpp: In function 'void solve()':
LM.cpp:249:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &N, &M);
                       ^
LM.cpp:252:43: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int x, y, z; scanf("%d%d%d", &x, &y, &z);
                                           ^

Subtask #1
2.0 / 2.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 37124 KB Output is correct
2 Correct 3 ms 37124 KB Output is correct
3 Correct 9 ms 37212 KB Output is correct
4 Correct 16 ms 37212 KB Output is correct
5 Correct 16 ms 37212 KB Output is correct
6 Correct 13 ms 37120 KB Output is correct
7 Correct 13 ms 37124 KB Output is correct
8 Correct 6 ms 37120 KB Output is correct
9 Correct 9 ms 37124 KB Output is correct
10 Correct 16 ms 37124 KB Output is correct
11 Correct 13 ms 37124 KB Output is correct
12 Correct 13 ms 37120 KB Output is correct
13 Correct 3 ms 37252 KB Output is correct
14 Correct 9 ms 37120 KB Output is correct
15 Correct 6 ms 37120 KB Output is correct
16 Correct 6 ms 37248 KB Output is correct
17 Correct 9 ms 37248 KB Output is correct
18 Correct 6 ms 37248 KB Output is correct
19 Correct 13 ms 37244 KB Output is correct
20 Correct 9 ms 37120 KB Output is correct
21 Correct 6 ms 37248 KB Output is correct
22 Correct 13 ms 37244 KB Output is correct
23 Correct 9 ms 37248 KB Output is correct
24 Correct 13 ms 37244 KB Output is correct
25 Correct 0 ms 36016 KB Output is correct
26 Correct 0 ms 36016 KB Output is correct
27 Correct 0 ms 36016 KB Output is correct
28 Correct 0 ms 36552 KB Output is correct

Subtask #2
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2000 ms 152912 KB Execution timed out
2 Halted 0 ms 0 KB -