oj.uz

답안 #22872

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
22872 2017-04-30T07:57:20 Z AcornCkiGs14004Team(#953, gs14004, cki86201, dotorya) Logistical Metropolis (KRIII5_LM) C++14
2 / 7
 2000 ms 115292 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 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;

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;
		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;
}

Compilation message

LM.cpp: In function 'void solve()':
LM.cpp:258: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:261: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 16 ms 36860 KB Output is correct
2 Correct 13 ms 36860 KB Output is correct
3 Correct 16 ms 36816 KB Output is correct
4 Correct 6 ms 36816 KB Output is correct
5 Correct 13 ms 36816 KB Output is correct
6 Correct 9 ms 36856 KB Output is correct
7 Correct 13 ms 36860 KB Output is correct
8 Correct 9 ms 36856 KB Output is correct
9 Correct 9 ms 36860 KB Output is correct
10 Correct 9 ms 36860 KB Output is correct
11 Correct 9 ms 36860 KB Output is correct
12 Correct 9 ms 36856 KB Output is correct
13 Correct 6 ms 36856 KB Output is correct
14 Correct 3 ms 36856 KB Output is correct
15 Correct 6 ms 36856 KB Output is correct
16 Correct 9 ms 36852 KB Output is correct
17 Correct 9 ms 36852 KB Output is correct
18 Correct 13 ms 36852 KB Output is correct
19 Correct 13 ms 36848 KB Output is correct
20 Correct 16 ms 36856 KB Output is correct
21 Correct 13 ms 36852 KB Output is correct
22 Correct 13 ms 36848 KB Output is correct
23 Correct 9 ms 36852 KB Output is correct
24 Correct 13 ms 36848 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 3 ms 36420 KB Output is correct

Subtask #2
0 / 5.0

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